八大排序分类

按照稳定性分类： 稳定性指的是，在等待排序的一堆数当中，有几个值相同的元素，排序之后，如果相等元素之间的先后顺序不会发生改变，排序就是稳定的。 如果先后顺序发生改变，排序就是不稳定的。 稳定的排序算法有：冒泡排序，插入排序，归并排序，基数排序。 不稳定的排序算法有：希尔排序，选择排序，堆排序和快速排序。

按照时间复杂度分类： O(n^2)级别：插入排序，选择排序，冒泡排序 ，希尔排序 O(nlogn)归并排序，堆排序和快速排序

插入排序

每次都把当前元素插入到左边已经排好序的数组当中，保证插入之后，左边的数组仍然有序。 插入元素和数组的初始顺序有关，如果数组已经部分有序了，需要交换的元素少。 最好情况下，数组已经有序，只需要N-1次比较，0次交换。 最坏情况下，数组是逆序的，需要n*(n-1)/2次交换，是N^2级别额交换次数。 平均时间复杂度是O(n^2) 稳定性分析：如果插入元素和前面的元素相同，会把插入元素放到相同元素的后面，相等元素的先后顺序没有发生改变，所以是插入排序是稳定的排序。

插入排序的算法步骤： 1、从第一个元素开始，认为这个元素已经被排序了 2、取出1下一个元素，在已经排序的元素里，从后往前扫描 3、在已经排序的数组中，如果这个元素大于新元素，就把这个元素移动到下一个位置。 4、一直往前找，如果找到一个元素小于等于新元素，就停止。 5、把新元素插入到这个位置。然后重复以上操作。

package com.company; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] arr = {2, 4, 6, 7, 1, 3}; System.out.println("Before sort" + Arrays.toString(arr)); insertSort(arr); System.out.println("After sort" + Arrays.toString(arr)); } public static void insertSort(int[] arr) { for(int i = 1; i < arr.length; i++) { //取出下一个元素，已经排序的序列中从后前移动 int temp = arr[i]; for(int j = i; i >= 0; j--) { if((j > 0) && (arr[j - 1] > temp)) { arr[j] = arr[j - 1];//把元素移动到后面的元素 System.out.println("Temping" + Arrays.toString(arr)); } else { //把新元素插入到这个位置之后 arr[j] = temp; System.out.println("sorting" + Arrays.toString(arr) ); break;//停止这次循环 } } } } }

运行结果如下

Before sort[2, 4, 6, 7, 1, 3] sorting[2, 4, 6, 7, 1, 3] sorting[2, 4, 6, 7, 1, 3] sorting[2, 4, 6, 7, 1, 3] Temping[2, 4, 6, 7, 7, 3] Temping[2, 4, 6, 6, 7, 3] Temping[2, 4, 4, 6, 7, 3] Temping[2, 2, 4, 6, 7, 3] sorting[1, 2, 4, 6, 7, 3] Temping[1, 2, 4, 6, 7, 7] Temping[1, 2, 4, 6, 6, 7] Temping[1, 2, 4, 4, 6, 7] sorting[1, 2, 3, 4, 6, 7] After sort[1, 2, 3, 4, 6, 7]

归并排序

归并排序是分治思想的典型应用，把一个问题分解成多个子问题，然后把子问题再次分解成更小的子问题。 把等待排序的序列分成很多个子序列，每一个子序列是有序的，然后把有序的子序列合并成整体有序的序列。 时间复杂度分析。对于长度为n的数组，拆分数组的时间复杂度是logn，合并子数组的过程时间复杂度是O(n)，所以整体的时间复杂度是O(nlogn)。

空间复杂度分析：递归过程中拆分的数组需要保存在内存中，空间复杂度是O(n)

从排序的流程可以看出，归并排序的性能和数据的状态无关，时间复杂度始终都是O(nlogn)。

package com.company; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] arr = {12, 11, 10, 2, 4, 6, 7, 1, 3}; System.out.println("Before sort" + Arrays.toString(arr)); //insertSort(arr); mergeSort(arr, 0, arr.length - 1); System.out.println("After sort" + Arrays.toString(arr)); } public static void mergeSort(int[] arr, int left, int right ) { int mid = left + (right - left)/2; if(left < right) { //左半边归并排序 mergeSort(arr, left, mid); //右半边归并排序 mergeSort(arr, mid+1, right); merge(arr, left, mid, right); } } public static void merge(int[] arr, int left, int mid , int right) { //创建临时数组 int[] temp = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; //把比较小的数先移入数组 while((i <= mid) && (j <= right)) { if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } //把左边的元素移入数组 while(i <= mid) { temp[k++] = arr[i++]; } //把右边的元素移入数组 while(j <= right) { temp[k++] = arr[j++]; } for(int k2 = 0; k2 <temp.length; k2++) { arr[left + k2] = temp[k2]; } } }

运行结果是

Before sort[12, 11, 10, 2, 4, 6, 7, 1, 3] After sort[1, 2, 3, 4, 6, 7, 10, 11, 12]

快速排序

package com.company; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] arr = {12, 11, 10, 2, 4, 6, 7, 1, 3}; System.out.println("Before sort" + Arrays.toString(arr)); //insertSort(arr); //mergeSort(arr, 0, arr.length - 1); quickSort(arr, 0, arr.length - 1); System.out.println("After sort" + Arrays.toString(arr)); } public static void quickSort(int[] arr, int start, int end) { if(arr == null || start >= end) { return ; } int partitionIndex = divide(arr, start, end); quickSort(arr, start, partitionIndex - 1); quickSort(arr, partitionIndex + 1, end); } public static int divide(int[] arr, int start, int end) { //选择基准元素 int base = arr[end]; //两个指针不相遇，就判断 while(start < end) { while(start < end && arr[start] <= base) { start++; } if(start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; end--; } while(start < end && arr[end] >= base) { end--; } if(start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; } } //相遇就返回 return end ; } }

代码运行结果

Before sort[12, 11, 10, 2, 4, 6, 7, 1, 3] After sort[1, 2, 3, 4, 6, 7, 10, 11, 12]

堆排序

堆排序需要两个过程，一是建立堆，另一个是调整堆。

初始化堆的时间复杂度是O(n)，更改堆元素之后，建立堆，需要循环n-1次，每次是从根节点往下寻找，所以时间复杂度是O(logn)，所以整体的时间复杂度是）O(nlogn) 没有用到辅助空间，堆排序是原地排序，时间复杂度是O(1)

package com.company; import java.util.Arrays; public class Sort { public static void main(String[] args) { int[] arr = {12, 11, 10, 2, 4, 6, 7, 1, 3}; System.out.println("Before sort" + Arrays.toString(arr)); //insertSort(arr); //mergeSort(arr, 0, arr.length - 1); //quickSort(arr, 0, arr.length - 1); heapSort(arr); System.out.println("After sort" + Arrays.toString(arr)); } public static void heapSort(int[] arr) { int n = arr.length; //最后一个有子节点的元素，下标是n/2 - 1.。这些元素都是根节点，有孩子节点，所以heapify的最后一项根节点位置是根据i变化的 for(int i = n/2 - 1; i >= 0; i--) { heapify(arr, n, i); } for(int i = n-1; i >= 0; i--) { //大顶堆的0位置元素最大，把最大的放到数组的最后 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; //调整的堆的大小是不断变化的,堆顶下标始终是0，堆调整的范围在缩小 heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i;//把最大值的下标，初始化为i int l = 2*i + 1; int r = 2*i + 2; //内部不做循环，外层调用者的来控制调用heapify的次数 if(l < n && arr[l] > arr[largest]) { largest = l; } if(r < n && arr[r] > arr[largest]) { largest = r; } if(largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } }

运行结果

Before sort[12, 11, 10, 2, 4, 6, 7, 1, 3] After sort[1, 2, 3, 4, 6, 7, 10, 11, 12]

参考资料

八大排序