衡量算法效能的维度

时间复杂度

  下面是一段非常简单的累加算法。

 int sum(int n) {
   
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
   
    sum = sum + i;
  }
  return sum;
 }

  算法都需要cpu来执行，在cpu中，每行代码都是执行类似的操作：读数据->运算->写数据，这次操作的耗时可能随着cpu的性能而变化。因为我们的目的主要是衡量算法的性能你，所以cpu性能影响忽略不计。接下来把一次循环操作的耗时定为unit_time。那么这个算法执行的时间就可以(2+2n)unit_time。随着n值的无线增大，2unit_time则可以忽略不记，则算法耗时主要就为2n*unit_time。
  大O时间复杂度表示：O复杂度不具体的表示算法的执行时间，只是表示算法随着数据量增长，执行时间的增长趋势，所以也叫做渐进时间复杂度，简称时间复杂度。所以上面的累加算法的时间复杂度可以表示为：O(n)

空间复杂度

  空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。除了需要计算的数据存储空间，额外申请的空间，这类空间是空间复杂度需要来表示的。例如:

void print(int n) {
   
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
   
    a[i] = i * i;
  }
  for (i = n-1; i >= 0; --i) {
   
    print out a[i]
  }
}

额外申请了int[n]，所以空间复杂度为O(n)

稳定性

  稳定性是指：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

冒泡排序

升序排序为例，第一个数据和第二个数据比较，第一个数>第二个数，发生数据替换。替换完后第二个继续和第三个比较，以此类推。直至所有数据完成排序。这样的排序方式，大的数据就像水泡一样上浮到水面，所以叫做冒泡排序。
附上演示地址：冒泡排序

private static void bubbleSort(int[] arr){
   
        //退出标志位：如果一次循环没有发生数据交换，则说明数组有序，可以推出
        boolean flag = true;
        for(int i=0;i<arr.length;i++){
   
            for(int j=0;j<arr.length-i-1;j++){
   
                if(arr[j]>arr[j+1]){
   
                   int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    //发生数据交换，则置为false
                    flag = false;
                }
            }
            //提前退出
            if(flag) break;
        }
    }
  1. 时间复杂度
    将for循环中的执行时间计为：unit_time。则整个耗时：O(n2)
  2. 空间复杂度
    只使用了一个辅助变量int temp，所以空间复杂度为：O(1)
  3. 稳定性
    因为相等的数据并不进行交换，所以是稳定算法。

选择排序

附上演示地址：选择排序

private static void selectionSort(int[] arr){
   
        for(int i=0;i<arr.length;i++){
   
            int index = i;
            //选出最小的数据
            for(int j=i+1;j<arr.length;j++){
   
                if(arr[index]>arr[j]){
   
                    index = j;
                }
            }
            //数据交换
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
  1. 时间复杂度
    将for循环中的执行时间计为：unit_time。则整个耗时：O(n2)
  2. 空间复杂度
    只使用了一个辅助变量int temp，所以空间复杂度为：O(1)
  3. 稳定性
    因为相等的数据也可能进行交换，所以是不稳定算法。

插入排序

附上演示地址：插入排序

private static void insertionSort(int[] arr){
   
        for(int i=0;i<arr.length;i++){
   
        	//插入到已经有序的排列中
            for(int j=i;j>0;j--){
   
                if(arr[j]<arr[j-1]){
   
                	//数据交换
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
  1. 时间复杂度
    将for循环中的执行时间计为：unit_time。则整个耗时：O(n2)
  2. 空间复杂度
    只使用了一个辅助变量int temp，所以空间复杂度为：O(1)
  3. 稳定性
    因为相等的数据并不进行交换，所以是稳定算法。

快速排序

附上演示地址：快速排序

private static void quickSort(int[] arr,int low,int high){
   
        int i = low;
        int j = high;
        if(low>=high) return;
        //选第一个数据为基数
        int temp = arr[low];
        while (i<j){
   
        	//从右开始选比基数小的
            while (arr[j]>=temp&&i<j){
   
                j--;
            }
            //从左开始，选比基数大的
            while (arr[i]<=temp&&i<j){
   
                i++;
            }
            //选出来后进行数据替换
            if(i<j){
   
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //跳出循环，现在i=j，i位置数据于基数数据交换，因为比基数小的都替换到基数的右边了。
        arr[low] = arr[i];
        arr[i] = temp;
        //现在i=j的左边都是小于等于arr[i]的，右边大于等于arr[i]的。
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }
  1. 时间复杂度
    时间复杂度：O(nlogn)
  2. 空间复杂度
    空间复杂度为：O(nlogn)
  3. 稳定性
    因为相等的数据也可能进行交换，所以是不稳定算法。