《八大排序算法总结与java实现》由会员分享，可在线阅读，更多相关《八大排序算法总结与java实现（50页珍藏版）》请在金锄头文库上搜索。
1、 北大青鸟华美官网： 概述因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法：我们讨论的这八大排序算法的实现可以参考我的 Github：SortAlgorithms，其中也包括了排序测试模块Test.java和排序算法对比模块Bench.java，大家可以试运行。它们都属于内部排序，也就是只考虑数据量较小仅需要使用内存的排序算法，他们之间关系如下：北大青鸟华美官网： 一、直接插入排序（Insertion Sort）插入排序的设计初衷是往有序的数组中快速插入一个新的元素往有序的数组中快速插入一个新的元素。
2、它的算法思想是：把要排序的数组分为了两个部分, 一部分是数组的全部元素(除去待插入的元素), 另一部分是待插入的元素; 先将第一部分排序完成, 然后再插入这个元素. 其中第一部分的排序也是通过再次拆分为两部分来进行的.北大青鸟华美官网： 插入排序由于操作不尽相同, 可分为 直接插入排序 , 折半插入排序(又称二分插入排序), 链表插入排序 , 希尔排序 。我们先来看下直接插入排序。1、基本思想直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。2、算法描述一般来说，插入排序都采用 in-place 在数组
3、上实现。具体算法描述如下：. 从第一个元素开始，该元素可以认为已经被排序 . 取出下一个元素，在已经排序的元素序列中从后向前扫描 . 如果该元素（已排序）大于新元素，将该元素移到下一位置 . 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置 . 将新元素插入到该位置后 . 重复步骤北大青鸟华美官网： 如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序插入排序的一个变种，称为二分查找插入排序。3、代码实现/* 插入排序* 1. 从第一个元素开始，该元素可以认为已经被排序* 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描* 3.
4、 如果该元素（已排序）大于新元素，将该元素移到下一位置* 4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置北大青鸟华美官网： * 5. 将新元素插入到该位置后* 6. 重复步骤 25* param arr 待排序数组*/public static void insertionSort(int arr)for( int i=0; i0; j- ) if( arrj-1 tj，tk=1；（一般初次取数组一般初次取数组半长，之后每次再减半，直到增量为半长，之后每次再减半，直到增量为 1） . 按增量序列个数 k，对序列进行 k 趟排序； . 每趟排序，根据对应的增量 ti，将待排序列
5、分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。3、代码实现以下是我自己的实现，可以看到实现很幼稚，但是好处是理解起来很简单。因为没有经过任何的优化，所以不建议大家直接使用。建议对比下方的维基百科官方实现代码，特别是步长取值策略部分。/* 希尔排序* 1. 选择一个增量序列 t1，t2，tk，其中 titj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为 1）* 2. 按增量序列个数 k，对序列进行 k 趟排序；* 3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，
6、分别对各子表进行直接插入排序。* 仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。北大青鸟华美官网： * param arr 待排序数组*/public static void shellSort(int arr)int gap = arr.length / 2;for (; gap 0; gap /= 2) /不断缩小 gap，直到 1 为止for (int j = 0; (j+gap) arrk+gap) int temp = arrk+gap; /交换操作arrk+gap = arrk;arrk = temp;System.out.println(“ Sorti
7、ng: “ + Arrays.toString(arr);北大青鸟华美官网： 注意： . 第一层 for 循环表示一共有多少个增量。增量的序列的个数，就是希尔排序的趟数。上面的增量序列为： arr.length/2, arr.length/2/2, arr.length/2/2/2, . 2, 1. 里层的两个 for 循环，实际上就是以一个 gap 拆分为一组的组内插入排序组内插入排序。下面是维基百科官方实现，大家注意 gap 步长取值部分：/* 希尔排序（Wiki 官方版）* 1. 选择一个增量序列 t1，t2，tk，其中 titj，tk=1；（注意此算法的 gap 取值）* 2. 按增量
8、序列个数 k，对序列进行 k 趟排序；* 3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。* 仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。* param arr 待排序数组北大青鸟华美官网： */public static void shell_sort(int arr) int gap = 1, i, j, len = arr.length;int temp;while (gap : 1, 4, 13, 40, 121, .for (; gap 0; gap /= 3) for (i = gap; i
9、 = 0 j -= gap)arrj + gap = arrj;arrj + gap = temp;以下是希尔排序复杂度:北大青鸟华美官网： 平均时间复杂度平均时间复杂度最好情况最好情况最坏情况最坏情况空间复杂度空间复杂度O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)三、选择排序（Selection Sort）从算法逻辑上看，选择排序是一种简单直观的排序算法，在简单选择排序过程中，所需移动记录的次数比较少。1、基本思想选择排序的基本思想：比较 + 交换。北大青鸟华美官网： 在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方
10、法中，选择排序属于非常好的一种。2、算法描述. 从待排序序列中，找到关键字最小的元素； . 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换； . 从余下的 N - 1 个元素中，找出关键字最小的元素，重复、步，直到排序结束。3、代码实现选择排序比较简单，以下是我自己的实现，跟官方版差不多，所以完全可以参考。/* 选择排序* 1. 从待排序序列中，找到关键字最小的元素；* 2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；* 3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复、步，直到排序结束。* 仅增量因子为 1 时，整个序列作为一个表来处理，表长
11、度即为整个序列的长度。* param arr 待排序数组北大青鸟华美官网： */public static void selectionSort(int arr)for(int i = 0; i = k(2i) ki = k(2i+1)把此序列对应的二维数组看成一个完全二叉树。那么堆的含义就是：完全二叉完全二叉树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。树中任何一个非叶子节点的值均不大于（或不小于）其左，右孩子节点的值。北大青鸟华美官网： 由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。因此我们可使用大顶堆进行升序排
12、序, 使用小顶堆进行降序排序。1、基本思想此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。2、算法描述. 先将初始序列 K1.n建成一个大顶堆, 那么此时第一个元素 K1 最大, 此堆为初始的无序区. . 再将关键字最大的记录 K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区 K1.n-1和有序区 Kn, 且满足 K1.n-1.keys 0; i-)max_heapify(arr, i);int temp = arr0; /堆顶元素(第一个元素)与 Kn 交换arr0
13、 = arri-1;arri-1 = temp;private static void max_heapify(int arr, int limit)if(arr.length = 0; parentIdx-)if(parentIdx * 2 = limit)北大青鸟华美官网： continue;int left = parentIdx * 2; /左子节点位置int right = (left + 1) = limit ? left : (left + 1); /右子节点位置，如果没有右节点，默认为左节点位置int maxChildId = arrleft = arrright ? left
14、 : right;if(arrmaxChildId arrparentIdx) /交换父节点与左右子节点中的最大值int temp = arrparentIdx;arrparentIdx = arrmaxChildId;arrmaxChildId = temp;System.out.println(“Max_Heapify: “ + Arrays.toString(arr);注注: x1 是位运算中的右移运算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x1 = Math.floor(x/2) .北大青鸟华美官网： 以上, . 建立堆的过程, 从 length/2 一直处理到 0,
15、时间复杂度为 O(n); . 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为 O(lgn); . 堆排序的过程由 n 次第步完成, 时间复杂度为 O(nlgn).平均时间复杂度平均时间复杂度最好情况最好情况最坏情况最坏情况空间复杂度空间复杂度O(nlog2n)O(nlog2n)O(nlog2n)O(1)Tips: 由于堆排序中初始化堆的过程比较次数较多由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列因此它不太适用于小序列.同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.五、冒泡排序（Bubble Sort）我想对于它每个学过 C 语言的都会了解，这可能是很多人接触的第一个排序算法。北大青鸟华美官网： 1
