冒泡排序

算法思想

首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换；然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换，以此类推，最终最大的数被交换到最后，一趟冒泡排序完成，经过多趟，冒泡排序完成。
交换类排序 - 图1

  1. public static void bubbleSortBase(int array[]){
  2.     int i, j, temp;
  3.     //一共需要比较n-1趟
  4.     for(i = 0; i < array.length-1; i++){
  5.         //因为要与后面一个比较，所以数组下标只能到n-1
  6.         for (j = 0; j < array.length-i-1; j++){
  7.             if (array[j] > array[j+1]){
  8.                 temp = array[j];
  9.                 array[j] = array[j+1];
  10.                 array[j+1] = temp;
  11.             }
  12.         }
  13.     }
  14. }

复杂度分析

时间复杂度：
最坏情况，待排序列逆序O(n2)
最好情况，待排序列有序O(n)
平均时间复杂度O(n2)
空间复杂度：O(1)。

  1.     /**
  2.      * 若一趟冒泡之后没有元素发生交换则认为排序完成
  3.      */
  4.     public static void bubbleSortFlag(int array[]){
  5.         int i, j, temp;
  6.         //标志位
  7.         boolean isSwap;
  8.         for(i = 0; i < array.length-1; i++){
  9.             isSwap = false;
  10.             //因为要与后面一个比较，所以数组下标只能到n-1
  11.             for (j = 0; j < array.length-i-1; j++){
  12.                 if (array[j] > array[j+1]){
  13.                     temp = array[j];
  14.                     array[j] = array[j+1];
  15.                     array[j+1] = temp;
  16.                     isSwap = true;
  17.                 }
  18.             }
  19.             if (!isSwap)
  20.                 break;
  21.         }
  22.     }
  1.     public static void bubbleSortDouble(int array[]){
  2.         //无序区范围下标
  3.         int minIndex = 0;
  4.         int maxIndex = array.length - 1;
  5.         //最后一次交换位置
  6.         int lastChange = array.length - 1;
  7.         //循环下标
  8.         int i, j;
  9.         //交换标志
  10.         boolean isSwap = false;
  11.         int temp;
  13.         for(i = 0; i < array.length-1; i++){
  14.             isSwap = false;
  15.             //最大值
  16.             for (j = minIndex; j < maxIndex; j++){
  17.                 if (array[j] > array[j+1]){
  18.                     temp = array[j];
  19.                     array[j] = array[j+1];
  20.                     array[j+1] = temp;
  21.                     isSwap = true;
  22.                     lastChange = j;
  23.                 }
  24.             }
  25.             if (!isSwap)
  26.                 break;
  27.             maxIndex = lastChange;
  28.             //最小值
  29.             for (j = maxIndex; j > minIndex; j--){
  30.                 if (array[j-1] > array[j]){
  31.                     temp = array[j];
  32.                     array[j] = array[j-1];
  33.                     array[j-1] = temp;
  34.                     isSwap = true;
  35.                 }
  36.             }
  37.             minIndex++;
  38.             if (!isSwap)
  39.                 break;
  40.         }
  41.     }

快速排序

通过多次划分实现排序，每一趟选择当前所有子序列中的一个关键字最为枢纽，将子序列中比枢纽晓得一道枢纽前边，比枢纽大的移到枢纽后边，当本趟所有子序列都被枢纽以上述规则划分完毕后会得到新的一组更短的子序列，它们成为下一趟划分的初始子序列
交换类排序 - 图2

  1. //划分
  2.     public static int partition(int array[], int left, int right){
  3.         int temp = array[left];
  5.         while (left < right){
  6.             //将右边比枢纽小的移到左边
  7.             while ((left < right) && array[right] >= temp)
  8.                 right--;
  9.             array[left] = array[right];
  10.             //将左边比枢纽打的移到右边
  11.             while ((left < right) && array[left] <= temp)
  12.                 left++;
  13.             array[right] = array[left];
  15.         }
  16.         array[left] = temp;
  17.         return left;
  18.     }
  20.     public static void quickSort(int array[], int left, int right){
  21.         if (left < right){
  22.             int pivot = partition(array,left,right);
  23.             quickSort(array,left,pivot-1);
  24.             quickSort(array,pivot+1,right);
  25.         }
  26.     }

复杂度分析

时间复杂度：快速排序最好情况下的时间复杂度为O(nlog2n)，待排序列有序越接近无序，本算法效率越高。最坏情况下的时间复杂度为O(n2)，待排序列越接近有序，本算法效率越低。平均时间复杂度为O(nlog2n)。
空间复杂度：O(nlog2n)。递归需要栈的辅助。