八大排序算法Java实现分析

## 0 概述 排序分为： - 内部排序，数据记录在内存中进行排序 - 外部排序，因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需访问外存 `时间复杂度为最差情况下的复杂度` 八大排序都是内部排序：  当n较大，应采用时间复杂度为 O(nlog2n) 的排序方法：快排、堆排和归排 `快速排序：目前基于比较的内部排序中被认为最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短 ` ### 稳定性 在值相等情况下，相对次序保持不变。 ## 1 插入排序—直接插入排序（Straight Insertion Sort） ### 基本思想 将一个记录插入到已排序好的有序表中，从而得到一个新且记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 ### 要点 设立哨兵，作为临时存储和判断数组边界之用。 ### 示例  元素相等的，把欲插入的元素放在相等元素的后面。 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序 所以插入排序稳定。 ### 实现 ```java public class InsertionSort { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } } ``` ### 效率 时间复杂度：`O（n^2）` 其他插入排序有二分插入排序，2-路插入排序。 常数项极低，所以样本容量很小时`(数组长度小于6)最快!`,Java 的 Collections.sort即是如此设计 ## 2 插入排序—希尔排序（Shell`s Sort） 1959 年由D.L.Shell 提出，相对直接排序有较大的改进，又叫**缩小增量排序**。 ### 思想 - 先将整个待排序的记录序列`分割`成为若干子序列分别进行直接插入排序 - 待整个序列中的记录“`基本有序`”时 - 再`对全体`记录进行依次直接插入排序  ### 实现 简单处理增量序列： `d = {n/2 ,n/4, n/8 .....1}`, n为要排序数的个数 - 先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列 - 每组中记录的`下标相差d`,对每组中元素进行`直接插入排序` - 再用一个较小的增量（d/2）对它进行分组 - 在每组中再进行`直接插入排序` - 继续不断`缩小增量`直至为1，最后使用`直接插入排序`完成排序 ```java /** * 直接插入排序的一般形式 * * @param int dk 缩小增量，如果是直接插入排序，dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; } } ``` 希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。 增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。 ## 3 选择排序—简单选择排序（Simple Selection Sort） ### 思想 在要排序的一组数中，选出最小/大的一个数与第1个位置的数交换 然后在剩下的数当中再找最小/大的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止  #### 操作 第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换； 第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换； 以此类推..... 第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换， 直到整个序列按关键码有序。 ### 实现 ```java /** * 数组的最小值 * * @return int 数组的键值 */ int SelectMinKey(int a[], int n, int i) { int k = i; for(int j=i+1 ;j< n; ++j) { if(a[k] > a[j]) k = j; } return k; } /** * 选择排序 * */ void selectSort(int a[], int n){ int key, tmp; for(int i = 0; i< n; ++i) { key = SelectMinKey(a, n,i); //选择最小的元素 if(key != i){ tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换 } print(a, n , i); } } ``` 简单选择排序的改进——二元选择排序 简单选择排序，每趟循环只能确定一个元素排序后的定位 我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下： 无稳定性!!! ## 4 选择排序—堆排序（Heap Sort） 树形选择排序，是对直接选择排序的有效改进 ### 思想 堆的定义：具有n个元素的序列（k1,k2,...,kn),当且仅当满足：  可见，**堆顶元素**（即第一个元素）必为最小项(小顶堆) 若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其孩子的值，根结点（堆顶元素）的值是最小(或最大)的 如： (a)大顶堆序列：（96, 83,27,38,11,09) (b)小顶堆序列：（12，36，24，85，47，30，53，91）  - 初始时把要排序的n个数的序列看作是一棵**顺序存储的二叉树（一维数组存储二叉树）** 调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大） - 然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素 - 依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为**堆排序**。 因此，实现堆排序需解决`两个问题`： 1\. 如何将n 个待排序的数`建堆` 2\. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个`新堆` 首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程 `调整小顶堆` 1. 设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素 将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏(根结点不满足堆的性质) 2. 将根结点与左、右子树中较小元素的进行交换 3. 若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法2. 4. 若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法2. 5. 继续对不满足堆性质的子树进行上述交换操作，直到叶结点，堆被建成 称这个自根结点到叶子结点的调整过程为`筛选`  再讨论对n 个元素初始`建堆`的过程 建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。 1）n 个结点的完全二叉树，则最后一个结点是第`n / 2`个结点的子树 2）筛选从第`n / 2`个结点为根的子树开始，该子树成为堆。 3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。 如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）   - 算法的实现 ```java package com.sss; import java.util.Arrays; /** * @author JavaEdge */ public class HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; swap(arr, 0, --size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); } } ``` 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置 所以堆排序有两个函数组成 - 一是建堆的渗透函数 - 二是反复调用渗透函数实现排序的函数 ```cpp void print(int a[], int n){ for(int j= 0; j