一、排序算法 - 图1

Java和Python对于对象的排序都是归并排序，因为是稳定的。

冒泡排序 时间复杂度为O(n^2)

  2. public static void sort(int arr[]) {
  3.     for(int i = 0; i < arr.length - 1; i++) {
  4.         for(int j = 0; j < arr.length - 1 - i; j++) {
  5.             int temp = 0;
  6.             if(arr[j] > arr[j+1]) {
  7.                 temp = arr[j];
  8.                 arr[j] = arr[j+1];
  9.                 arr[j+1] = temp;
  10.             }
  11.         }
  12.     }
  13. }
  14. // 优化,设置一个临时变量来标记该数组是否已经有序，如果有序就直接进入下一次遍历。
  15. public static void sort(int arr[]) {
  16.     for(int i = 0; i < arr.length - 1; i++ ) {
  17.         boolean isSort = true;
  18.         for(int j = 0; j < arr.length - 1 - i; j++ ){
  19.             int temp = 0;
  20.             if(arr[j] > arr[j + 1]){
  21.                 temp = arr[j]; 
  22.                 arr[j] = arr[j + 1]; 
  23.                 arr[j + 1] = temp; 
  24.                 isSort = false;
  25.             } 
  26.         }
  27.         if(isSort){
  28.             break;
  29.         }
  30.     } 
  31. }

选择排序 时间复杂度为O(n^2)

  1. public static void sort(int arr[]) {
  2.     for (int i = 0; i < arr.length; i++ ) {
  3.         int min = i;    //最⼩小元素的下标
  4.         for(int j = i + 1; j < arr.length; j++ ) {
  5.             if(arr[j] < arr[min]) { 
  6.                 min = j;    //找最⼩小值下标
  7.             } 
  8.         }
  9.         //交换位置
  10.         int temp = arr[i]; 
  11.         arr[i] = arr[min]; 
  12.         arr[min] = temp;
  13. }

插入排序 时间复杂度为O(n^2)

  1. public static void sort(int[] arr) {
  2.        int n = arr.length;
  4.        for(int i = 1; i < n; ++i) {
  5.            int value = arr[i];
  6.            int j = 0;
  8.            for(j = i -1; j >= 0; j--) {
  9.                if(arr[j] > value) {
  10.                    arr[j+1] = arr[j];
  11.                } else {
  12.                    break;
  13.                }
  14.            }
  15.            arr[j+1] = value;
  16.        }
  17.    }

希尔排序 时间复杂度(n)，按照间隔排，间隔里面按照插入排序排

  1.  public static void sort(int[] arr) {
  2.         int length = arr.length;
  3.         int gap = 1;
  5.         while (gap < length) {
  6.             gap = gap * 3 + 1;
  7.         }
  8.         while (gap > 0) {
  9.             for (int i = gap; i < length; i++) { 
  10.                 int tmp = arr[i];
  11.                 int j = i - gap;
  13.                 while (j >= 0 && arr[j] > tmp) {
  14.                     arr[j + gap] = arr[j];
  15.                     j -= gap;
  16.                 }
  17.                 arr[j + gap] = tmp;
  18.             }
  19.             gap = gap / 3;
  20.         }
  21.     }

归并排序 时间复杂度为 O(nlogn)

  1. public static void sort(int[] arr) {
  2.     int[] tempArr = new int[arr.length];
  3.     sort(arr, tempArr, 0, arr.length - 1);
  4. }
  5. /**
  6. * 归并排序
  7. * @param arr 排序数组
  8. * @param tempArr 临时存储数组
  9. * @param startIndex 排序起始位置
  10. * @param endIndex 排序终⽌止位置 
  11. */
  13. private static void sort(int[] arr, int[] tempArr, int startIndex, int endIndex) {
  14.     if (endIndex <= startIndex) {
  15.         return;
  16.     }
  18.     int middleIndex = startIndex + (endIndex - startIndex) / 2;
  20.     sort(arr, tempArr, startIndex, middleIndex);
  21.     sort(arr, tempArr, middleIndex + 1, endIndex);
  22.     merge(arr, tempArr, startIndex, middleIndex, endIndex);
  23. }
  25. /**
  26. * 归并
  27. * @param arr 排序数组
  28. * @param tempArr 临时存储数组
  29. * @param startIndex 归并起始位置 * @param middleIndex 归并中间位置 * @param endIndex 归并终⽌止位置
  30. */
  31. private static void merge(int[] arr, int[] tempArr, int startIndex, int middleIndex, int endIndex) {
  32.     // 复制要合并的数据
  33.     for(int s = startIndex; s <= endIndex; s++) {
  34.         tempArr[s] = arr[s];
  35.     }
  36.     // 左边⾸首位下标
  37.     int left = startIndex; 
  38.     // 右边⾸首位下标   
  39.     int right = middleIndex + 1;
  41.     for (int k = startIndex; k <= endIndex; k++) {
  42.         if (left > middleIndex) {
  43.             // 如果左边的⾸首位下标⼤大于中部下标，证明左边的数据已经排完了了。
  44.             arr[k] = tempArr[right++];
  45.         } else if (right > endIndex) {
  46.             // 如果右边的⾸首位下标⼤大于了了数组⻓长度，证明右边的数据已经排完了了。
  47.             arr[k] = tempArr [left++];
  48.         } else if (tempArr[right] < tempArr[left]) {
  49.             // 将右边的⾸首位排⼊入，然后右边的下标指针+1
  50.             arr[k] = tempArr[right++];
  51.         } else {
  52.             // 将左边的⾸首位排⼊入，然后左边的下标指针+1
  53.             arr[k] = tempArr[left++];
  54.         }
  55.     }
  56. }

快速排序 时间复杂度为O(nlogn)

  1. private static void quickSort(int[] arr, int left, int right) {
  3.     if (left < right) {
  4.         int i, j, x;
  5.         i = left;
  6.         j = right;
  7.         x = arr[i];
  9.         while (i < j) {
  10.             // 从右向左找到第一个小于x的数
  11.             while (i < j && arr[j] > x) j--;
  12.             if (i < j)
  13.                 arr[i++] = arr[j];
  15.             // 从左向右找到第一个大于x的数
  16.             while (i < j && arr[i] < x) i++;
  17.             if (i < j)
  18.                 arr[j--] = arr[i];
  19.         }
  20.         arr[i] = x;
  22.         quickSort(arr, left,i - 1);
  23.         quickSort(arr,i + 1, right);
  24.     }
  25. }

桶排序，不常用，复杂，

主要应用为计数排序和基数排序

计数排序，求众数

非比较思想、量大数小

  1. private static int getMax(int[] a) {
  2.         int max;
  4.         max = a[0];
  5.         for (int i = 1; i < a.length; i++)
  6.             if (a[i] > max)
  7.                 max = a[i];
  9.         return max;
  10. }
  12. public static int[] sort(int[] a, int max) {
  13.     int[] count = new int[++max];
  14.     int[] result = new int[a.length];
  16.     if (a == null || max < 1)
  17.         return null;
  19.     // 1. 计数
  20.     for(int i = 0; i < a.length; i++) 
  21.         count[a[i]]++; 
  23.     // 2. 排序，稳定
  24.     for (int i = 1; i < count.length; i++) {
  25.         count[i] = count[i] + count[i-1];
  26.     }
  28.     for (int i = a.length - 1; i >= 0; i--) {
  29.             result[--count[a[i]]] = a[i];
  30.     }
  32.     return result;
  33. }

基数排序

非比较思想、桶思想的一种、多关键字排序

堆排序，最大堆通常被用来进行”升序”排序，而最小堆通常被用来进行”降序”排序

  1. public static void maxHeapDown(int[] a, int start, int end) {
  2.     int c = start;            // 当前(current)节点的位置
  3.     int l = 2 * c + 1;        // 左(left)孩子的位置
  4.     int tmp = a[c];            // 当前(current)节点的大小
  6.     for (; l <= end; c = l,l = 2 * l + 1) {
  7.         // "l"是左孩子，"l+1"是右孩子
  8.     if (l < end && a[l] < a[l+1])
  9.         l++;        // 左右两孩子中选择较大者，即m_heap[l+1]
  10.         if (tmp >= a[l])
  11.             break;        // 调整结束
  12.         else {            // 交换值
  13.             a[c] = a[l];
  14.             a[l]= tmp;
  15.         }
  16.     }
  17. }
  19. public static void heapSortAsc(int[] a, int n) {
  20.     int i,tmp;
  22.     // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
  23.     for (i = n / 2 - 1; i >= 0; I--)
  24.         maxHeapDown(a, i, n-1);
  26.     // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
  27.     for (i = n - 1; i > 0; I--) {
  28.         // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
  29.         tmp = a[0];
  30.         a[0] = a[i];
  31.         a[i] = tmp;
  32.         // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
  33.         // 即，保证a[i-1]是a[0...i-1]中的最大值。
  34.         maxHeapDown(a, 0, i-1);
  35.     }
  36. }