[toc]

总览

image.png

稳定： 冒泡、插入、归并、基数

不稳定 选择、快速、希尔、堆

名词解释

  • n: 数据规模
  • k：桶个数
  • In-place：占用常用内存
  • Out-place：占用额外内存

基础排序算法

主程序代码

  1. package com.zzfan.sort;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         int[] arr = new int[10];
  6.         SetInitial(arr);
  7.         System.out.println("----排序前-----");
  8.         Sout(arr);
  9.         System.out.println("----排序后-----");
  10.         arr = BubbleSort.sort(arr);
  11.         Sout(arr);
  12.     }
  14.     private static void SetInitial(int[] arr) {
  15.         for (int i = 0; i < arr.length; i++) {
  16.             arr[i] = (int) (Math.random() * 100);
  17.         }
  18.     }
  20.     private static void Sout(int[] arr) {
  21.         for (int anArr : arr) {
  22.             System.out.print(anArr + " ");
  23.         }
  24.         System.out.println();
  25.     }
  26. }

1 冒泡排序

冒泡.gif
代码

  1. public class BubbleSort {
  3.     public static int[] sort(int[] sourceArray)  {
  4.         // 对 arr 进行拷贝，不改变参数内容
  5.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  7.         for (int i = 1; i < arr.length; i++) {
  8.             // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
  9.             boolean flag = true;
  11.             for (int j = 0; j < arr.length - i; j++) {
  12.                 if (arr[j] > arr[j + 1]) {
  13.                     int tmp = arr[j];
  14.                     arr[j] = arr[j + 1];
  15.                     arr[j + 1] = tmp;
  16.                     flag = false;
  17.                 }
  18.             }
  19.             if (flag) {
  20.                 break;
  21.             }
  22.         }
  23.         return arr;
  24.     }
  25. }

2 选择排序

选择.gif
代码

  1. package com.zzfan.sort;
  3. import java.util.Arrays;
  5. public class SelectionSort {
  6.     public static int[] sort(int[] sourceArray) {
  7.         int arr[] = Arrays.copyOf(sourceArray, sourceArray.length);
  8.         //一层循环基本都是N-1轮
  9.         for (int i = 0; i < arr.length - 1; i++) {
  10.             int min = i;
  11.             for (int j = i + 1; j < arr.length; j++) {
  12.                 if (arr[j] < arr[min]) {
  13.                     min = j;
  14.                 }
  15.             }
  16.             if (i != min) {
  17.                 int tmp = arr[i];
  18.                 arr[i] = arr[min];
  19.                 arr[min] = tmp;
  20.             }
  21.         }
  22.         return arr;
  23.     }
  24. }
  25. //关键点在于找最小下标，基本都是在一层循环里面搞事情。

3 插入排序

插入.gif
代码

  1. package com.zzfan.sort;
  3. import java.util.Arrays;
  5. public class InsertSort {
  6.     public static int[] sort(int[] sourceArray) {
  7.         int arr[] = Arrays.copyOf(sourceArray, sourceArray.length);
  8.         for (int i = 1; i < arr.length; i++) {
  9.             int tmp = arr[i];
  10.             int j = i;
  11.             while (j > 0 && tmp < arr[j - 1]) {//前面的大
  12.                 arr[j] = arr[j - 1];
  13.                 j--;
  14.             }
  15.             if (j != i) {
  16.                 arr[j] = tmp;
  17.             }
  18.         }
  19.         return arr;
  20.     }
  21. }
  22. //后面的拿下来，前面的移到后面，后面的再放上去（放前面）

4 希尔排序

升级版的插入排序，先分组，后插入。

代码

  1. package com.zzfan.sort;
  3. import java.util.Arrays;
  5. public class ShellSort {
  6.     public static int[] sort(int[] sourceArray) {
  7.         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  8.         int gap = 1;
  9.         while (gap < arr.length / 3) {
  10.             gap = gap * 3 + 1;
  11.         }
  12.         while (gap > 0) {
  13.             for (int i = gap; i < arr.length; i++) {
  14.                 int tmp = arr[i];
  15.                 int j = i - gap;
  16.                 while (j >= 0 && arr[j] > tmp) {//前面的大
  17.                     arr[j + gap] = arr[j];
  18.                     j -= gap;
  19.                 }
  20.                 arr[j + gap] = tmp;
  21.             }
  22.             gap = (int) Math.floor(gap / 3);
  23.         }
  24.         return arr;
  25.     }
  26. }

排序算法（重要）

1 归并排序

归并.gif
代码

  1. package com.zzfan.sort;
  3. import java.util.Arrays;
  5. public class MergeSort {
  7.     static int[] sort(int[] arr) {
  8.         int len = arr.length;
  9.         if (len < 2) {
  10.             return arr;
  11.         }
  12.         int mid = len / 2;
  13.         int[] left = Arrays.copyOfRange(arr, 0, mid);
  14.         int[] right = Arrays.copyOfRange(arr, mid, len);
  15.         return merge(sort(left), sort(right));
  16.     }
  17.     private static int[] merge(int[] left, int[] right) {
  18.         int[] result = new int[left.length + right.length];
  19.         int i = 0;
  20.         while (left.length > 0 && right.length > 0) {
  21.             if (left[0] <= right[0]) {
  22.                 result[i++] = left[0];
  23.                 left = Arrays.copyOfRange(left, 1, left.length);
  24.             } else {
  25.                 result[i++] = right[0];
  26.                 right = Arrays.copyOfRange(right, 1, right.length);
  27.             }
  28.         }
  29.         while (left.length > 0) {
  30.             result[i++] = left[0];
  31.             left = Arrays.copyOfRange(left, 1, left.length);
  32.         }
  33.         while (right.length > 0) {
  34.             result[i++] = right[0];
  35.             right = Arrays.copyOfRange(right, 1, right.length);
  36.         }
  37.         return result;
  38.     }
  39. }

2 快速排序

快速.gif
代码_01

  1. package com.zzfan.sort;
  3. public class QuickSort {
  4.     static void quickSort(int[] arr, int low, int high)  {
  5.         int i, j, pivot;
  6.         if (low > high) {
  7.             return;
  8.         }
  9.         i = low;
  10.         j = high;
  11.         pivot = arr[low];
  12.         while (i < j) {
  13.             while (arr[j] >= pivot && i < j) {
  14.                 j--;
  15.             }
  16.             while (arr[i] <= pivot && i < j) {
  17.                 i++;
  18.             }
  19.             if (i < j) {
  20.                 Swap(arr, i, j);
  21.             }
  22.         }
  23.         arr[low] = arr[i];
  24.         arr[i] = pivot;
  25.         quickSort(arr, low, j - 1);
  26.         quickSort(arr, j + 1, high);
  27.     }
  29.     private static void Swap(int[] arr, int i, int j) {
  30.         int tmp = arr[i];
  31.         arr[i] = arr[j];
  32.         arr[j] = tmp;
  33.     }
  34. }

代码_02

  1. package com.zzfan.sort;
  3. public class QuickSort_02 {
  5.     static void sort(int[] sourceArray) {
  6.         quickSort(sourceArray, 0, sourceArray.length - 1);
  7.     }
  8.     private static int[] quickSort(int[] arr, int left, int right)  {
  9.         if (left < right) {
  10.             int partitionIndex = partition(arr, left, right);
  11.             quickSort(arr, left, partitionIndex - 1);
  12.             quickSort(arr, partitionIndex + 1, right);
  13.         }
  14.         return arr;
  15.     }
  17.     private static int partition(int[] arr, int left, int right) {
  18.         int pivot = left;
  19.         int index = pivot + 1;
  20.         for (int i = index; i <= right; i++) {
  21.             if (arr[i] <= arr[pivot]) {
  22.                 Swap(arr, i, index);
  23.                 index++;
  24.             }
  25.         }
  26.         Swap(arr, pivot, index - 1);
  27.         return index - 1;
  28.     }
  29.     private static void Swap(int[] arr, int i, int j) {
  30.         int tmp = arr[i];
  31.         arr[i] = arr[j];
  32.         arr[j] = tmp;
  33.     }
  34. }

3 堆排序

堆.gif
代码

  1. package com.zzfan.sort;
  3. public class HeapSort {
  4.     static void sort(int[] sourceArr) {
  6.         bulid_heap(sourceArr, sourceArr.length);
  7.         for (int i = sourceArr.length - 1; i >= 0; i--) {
  8.             Swap(sourceArr, 0, i);
  9.             heapify(sourceArr, i, 0);
  10.         }
  11.     }
  12.     //n:数组元素个数
  13.     public static void bulid_heap(int[] tree, int n) {//创建一个树
  14.         int last_node = n - 1;
  15.         int parent_node = (last_node - 1) / 2;
  16.         for (int i = parent_node; i >= 0; i--) {
  17.             heapify(tree, n, i);
  18.         }
  19.     }
  20.     //n:数组元素个数，i：对第i个节点进行heapify()
  21.     public static void heapify(int[] arr, int n, int i) {
  22.         if (i >= n) {
  23.             return;
  24.         }
  25.         int left = 2 * i + 1;
  26.         int right = 2 * i + 2;
  27.         int max = i;    //对某个节点做heapify时，就是把该节点当作了父节点。
  28.         if (left < n && arr[left] > arr[max]) {
  29.             max = left;
  30.         }
  31.         if (right < n && arr[right] > arr[max]) {
  32.             max = right;
  33.         }
  34.         if (max != i) {
  35.             Swap(arr, max, i);
  36.             heapify(arr, n, max);
  37.         }
  38.     }
  40.     private static void Swap(int[] arr, int i, int j) {
  41.         int tmp = arr[i];
  42.         arr[i] = arr[j];
  43.         arr[j] = tmp;
  44.     }
  45. }

排序算法（其他）

1 计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数.gif

2 桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

3 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数.gif
基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；