堆排序算法 七种经典排序算法最全攻略

经典排名算法在面试中占有很大比重，也是基础。包括冒泡排序、插入排序、选择排序、希尔排序、合并排序、快速排序和堆排序。希望能帮助到有需要的同学。整个程序用Java实现。

本文中的所有排序实现都是从小到大默认的。

首先，泡沫不要进行泡沫分类

简介:

气泡排序的原理很简单。它重复访问要排序的序列，一次比较两个元素，如果它们的顺序错误，就交换它们。

步骤:

比较相邻元素。如果第一个比第二个大，就换。

对第0到第(n-1)个数据执行相同的操作。此时，最大的数字“浮动”到数组的最后一个位置。

对除最后一个元素之外的所有元素重复上述步骤。

一次对越来越少的元素重复上述步骤，直到没有要比较的数字对。

/**

*冒泡排序算法

*原理是相邻号码成对比较，按从小到大或从大到小的顺序交换，这样一趟旅行后，最大或最小的号码交换到最后一个位置，然后从开始到倒数第二个位置结束进行成对比较交换

* @param nums排序数组

* @param n数组长度

*最坏情况:O(n2)如果气泡排序没有优化，最好的情况是O(n2)，优化后最好的情况是O(n)

*/

public void Bullersort(int[]nums，int len){

for(int I = 0；i<。len-1；I++){ //一个比较

for(int j = 0；j<。& ltstrong>。len-1-i<。/strong>。；J++){ //为了比较，每次最大值都放在后面，下次比较后不需要比较I的个数。

int temp = nums[j]；

if(nums[j]>nums[j+1]){

nums[j]= nums[j+1]；

nums[j+1]= temp；

}

}

}system.out.println("冒泡排序:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

但是，上面的代码有两种优化方案。

优化1:如果某次遍历没有数据交换，说明已经排序了，不用再迭代了。用标签记录该状态(程序如下)。

优化二:记录某次遍历的最后一次数据交换位置。这个位置之后的数据显然是有序的，不需要排序。因此，下一个周期的范围可以通过记录最后一次数据交换的位置来确定(“j

public void better bulletorsort(int[]nums，int len){

布尔标志；

flag = true

for(int I = 0；i<。len-1和& amp旗帜；I++){ // A比较如果前面的比较没有交换，说明顺序安排在后面，不用再比较了

flag = false

for(int j = 0；j<。len-1-I；J++){ //为了比较，每次最大值都放在后面，下次比较后不需要比较I的个数。

int temp = nums[j]；

if(nums[j]>nums[j+1]){

nums[j]= nums[j+1]；

nums[j+1]= temp；

flag = true

}

}

}

System.out.println("优化气泡排序:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

第二，选择排序选择开始

简介:

选择排序无疑是最简单直观的排序。工作原理如下。

步骤:

在未排序的序列中找到最小的(大的)元素，并将其存储在排序序列的开头。

然后继续从剩余的未排序元素中搜索最小的(大的)元素，然后把它放在排序序列的末尾。

以此类推，直到所有元素都被排序。

& ltspan style = " font-size:14px；font-weight: normal>。/**

*选择排序算法

*基本思路是从每次行程要排序的记录中选择关键字最小的记录，放在排序后的子序列前面，直到所有记录排序完毕。

* @param nums排序数组

* @param n数组长度

*最坏情况:0(N2)，最好情况:0(N2)

*/

public void SelectSort(int[] nums，int len){

for(int I = 0；i<。leni++){

int min = nums[I]；//每次行程的最小值暂定为nums[i]

int index = I；//记录最小值的索引值

for(int j = I+1；j<。lenJ++){ //开始比较:从i+1位置到数组末尾比较，找出最小值，记录位置

if(nums[j] <。min){

min = nums[j]；

index = j；

}

}

//用最小值交换nums[i]

nums[index]= nums[I]；

nums[I]= min；

}

system . out . println(" select sort:")；

for (int i : nums) {

system . out . print(I+" ")；

}

} & lt/span>。

第三，插入排序插入排序

简介:

插入排序的工作原理是，对于每个未排序的数据，在排序后的序列中从后往前扫描，找到对应的位置，插入。

步骤:

从第一个元素开始，可以认为这个元素已经排序

取出下一个元素，按照元素的排序顺序从后向前扫描

如果扫描的元素(已排序)大于新元素，则将该元素向后移动一位

重复步骤3，直到找到排序元素小于或等于新元素的位置

将新元素插入此位置后，

重复步骤2~5

/**

*插入排序算法

* @param nums排序数组

* @param n数组长度

*最差情况:输入数组已被倒o排序(N2)；最佳情况:输入数组排序为o(n)；平均情况:0(N2)

*因为插入排序的内部循环非常紧凑，所以对于小规模输入，插入排序是一种非常快速的排序算法

*/

public void InsertSort(int[] nums，int len){

int j；

for(int I = 1；i<。leni++){

int temp = nums[I]；

for(j = I；j>。0;j - ){

if(temp & lt；nums[j-1]){

nums[j]= nums[j-1]；//将nums[i]之前大于nums[i]的所有值移回一位

}

否则中断；

}

//在移动所有大于nums[i]的值后，j只需指向大于nums[i]的前面位置

nums[j]= temp；

}

system . out . println(" insert sort:")；

for (int i : nums) {

system . out . print(I+" ")；

}

}

第四，希尔排序壳排序

简介:

希尔排序，也称为降序递增排序算法，本质上是分组插入排序。是唐纳德·谢尔在1959年提出的。希尔排序是一种不稳定的排序算法。

希尔排序的基本思想是在一个表中列出数组，并分别插入和排序列，重复这个过程，但每次使用更长的列(步长更长，列更少)。最后整个表只有一列。数组转换成表的目的是为了更好的理解算法，算法本身就是用数组来排序的。

例如，假设有这样一组数字

[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

如果我们以5的步长开始排序，我们可以通过将这个列表放在一个有5列的表中来更好地描述算法，这样它们应该是这样的:

13 14 94 33 82

25 59 94 65 23

45 27 73 25 39

10

然后我们对每一列进行排序:

10 14 73 25 23

13 27 94 33 39

25 59 94 65 82

45

当以上四行数字按顺序连接在一起时，我们得到:

[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]

。此时，10已经移动到正确的位置，然后按照3:

10 14 73

25 23 13

27 94 33

39 25 59

94 65 82

45

排序后，它变成:

10 14 13

25 23 33

27 25 59

39 65 73

45 94 82

94

最后按1步排序(此时简单插入排序)。

/**

*希尔排序算法

* @param nums排序数组

* @param n数组长度

*最差情况:0(N2)使用Hibbard增量的最差情况:0(n = 3/2)

*/

public void ShellSort(int[] nums，int len){

int增量；

int temp，I，j；

for(increment = len/2；增量>。0;增量/= 2){ //增量为len/2len/4len/8...一

for(I =增量；i<。lenI++){ //插入并排序每个子序列

temp = nums[I]；

for(j = I；j>。=增量；j -=增量){

if(temp & lt；nums[j-increment]){

nums[j]= nums[j-increment]；

}

其他

打破；

}

nums[j]= temp；

}

}

system . out . println(" Hill Sort:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

动词 （verb的缩写）合并排序合并排序

简介:

合并排序是分治法的典型应用。

合并成

排序的思想是先交付

返回

分解数组，然后

接近

和数组。

考虑先合并两个有序数组。基本思路是比较两个数组的前数，先取较小的那个。取完之后，对应的指针会向后移动一位。然后比较，直到一个数组是空，最后复制另一个数组的剩余部分。

考虑递归分解，基本思想是将数组分解成

左边的

和

正确的

如果这两个数组的内部数据是有序的，那么这两个数可以通过上述合并数组的方法进行合并排序。如何让这两个数组内部有序？可以进一步分为两部分，直到分解后的群只包含一个元素，此时认为群是有序的。然后合并并排序两个相邻的组。

/**

*合并排序算法

*对待序列R[0...n-1]排序为n个长度为1的有序序列，将相邻有序表成对合并，得到n/2个长度为2的有序表；再次合并这些有序序列，

*得到长度为4的n/4有序序列；如此反复，最终得到长度为n的有序序列。

*总结一下，合并排序其实有两件事要做:(1)“分解”——一次把序列分成两半。(2)“合并”——将分割后的序列片段成对合并后进行排序。

* @param nums

* @param透镜

* O(nlogn)

*/

public void MergeSort(int[] nums，int len){

sort(nums，0，len-1)；

system . out . println(" merge sort:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

//将一个数组按段分成两个数组

public void sort(int[] nums，int low，int high){

int mid =(高+低)/2；

if(低& lt高){

排序(nums，low，mid)；

排序(nums，中间+1，高)；

合并(nums，低，中，高)；

}

}

//按节排序，然后重新组合在一起

public void merge(int[] array，int low，int mid，int high){

int i =低电平；//第一个序列的下标

int j = mid+1；//第二个序列的下标

int k = 0；//第三个序列的下标

int[]array 2 = new int[high-low+1]；//新序列

while(I & lt；=mid &。& ampj<。=high){ //比较两个子序列的首元素，取较小的一个进入新序列，然后跳过旧序列中较小的值，开始下一次比较

if(array[I]& lt；= array[j]){

array 2[k++]= array[i++]；

}

else{

array 2[k++]= array[j++]；

}

}

if(I & lt；= mid){ //表示以上是J溢出退出循环，也就是序列1还没有比较。

while(I & lt；=mid){ //如果第一个序列没有被扫描，将其全部复制到合并的序列中

array 2[k++]= array[i++]；

}

}

else if(j & lt；=高){

while(j & lt；=high){ //如果第二个序列没有被扫描，将其全部复制到合并的序列中

array 2[k++]= array[j++]；

}

}

for(k = 0；k<。array 2 . length；k++){

array[k+low]= array 2[k]；//将按段排序的新数组复制到以前的数组中

}

}

第六，快速排序快速排序

简介:

快速排序通常比其他同样是ο (n log n)的算法快，所以经常使用。而且快速排序采用分而治之的思想，所以在很多笔试面试中经常能看到快速排序的影子。可见掌握快排很重要。

步骤:

从系列中选出一个元素作为参考编号。

在分割过程中，大于参考数的数字放在右边，小于或等于参考数的数字放在左边。

然后在左右区间递归执行第二步，直到每个区间只有一个数字。

/**

*快速分类

*快速排序的思路是分而治之。快速排序就是找一个元素(理论上可以找任意一个)作为支点，

*然后对数组进行分区，使基准左侧元素的值不大于基准值，基准右侧元素的值不小于基准值，这样作为基准的元素排序后调整到正确的位置。

*递归快速排序，排序后将其他n-1个元素调整到正确的位置。最后，每个元素排序后都在正确的位置，排序完成。

*所以快速排序的核心算法是分区操作，也就是如何调整基准的位置，调整返回基准的最终位置，从而分治递归。

* @param nums

* @param透镜

* O(NlogN)

*/

public void Quickort(int[]nums，int len){

Qsort(nums，0，len-1)；

System.out.println("快速排序:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

public void Qsort(int[] nums，int left，int right) {

if(左>;右)返回；

int pivot = nums[left]；

int i = left

int j = right

while(I & lt；j){

while(nums[j]>=枢轴& amp& ampi<。J){ //从右向左找一个小于nums[i]的数

j-；

}

nums[I]= nums[j]；//找到后交换

while(nums[I]& lt；=枢轴& amp& ampi<。J){ //从左到右找一个大于nums[j]的数

i++；

}

nums[j]= nums[I]；//找到后交换

}

//而在执行之后，必然有i==j = J。

nums[I]= pivot；//重置参考号

Qsort(nums，左侧，I-1)；//递归处理左侧

Qsort(nums，i+1，右)；//递归处理右侧

}

七、堆排序堆

简介:

堆排序常用于前K个问题。堆排序是利用二进制堆的数据结构实现的，虽然本质上是一维数组。二进制堆是一个近似完整的二叉树。

二进制堆栈具有以下属性:

父节点的键值总是大于或等于(小于或等于)任何子节点的键值。

每个节点的左右子树都是二进制堆(最大堆和最小堆)。

步骤:

Build_Max_Heap:如果数组下标范围是0~n，考虑到单个元素是一个很大的根堆，从下标开始

n/2

起始元素都是大根桩。所以就从

n/2-1

首先依次向前构造根堆，以保证在构造一个节点时，其左右子树已经是根堆。

HeapSort:因为堆是由数组模拟的。得到一个很大的根堆后，数组内部并不有序。因此，需要对堆数组进行排序。思路是去掉根节点，做最大堆调整的递归运算。将是第一次

堆[0]

和

堆[n-1]

交换，对吗

堆[0...n-2]

做最大的调整。第二次将是

堆[0]

和

堆[n-2]

交换，对吗

堆[0...n-3]

做最大的调整。重复此操作，直到

堆[0]

和

堆[1]

交换。因为每次最大数合并到下面的有序区间，所以运算后整个数组都是有序的。

Max heap adjust (Max_Heapify):这个方法是为上面两个过程调用提供的。目的是调整堆的末端子节点，使子节点始终小于父节点。

/**

*堆排序算法(最大堆)

* @param nums排序数组

* @param n数组长度

*时间复杂度O(nlogn)

*先构建最大的堆，然后循环删除堆根节点上的最大值，并移动到堆的末尾，将堆的长度减少一，然后开始下一次删除根节点

*/

public void HeapSort(int[] nums，int len){

//构建最大堆

for(int I = len/2；i>。=0;i - ){

PerDoWn(nums，I，len)；

}

//循环，每次改变根节点和最后一个节点的位置

for(int I = len-1；i>。=1;i - ){

//Swap(nums[0]，nums[i])交换nums[0]和nums[i]

int temp = nums[0]；

nums[0]= nums[I]；

nums[I]= temp；

percDown(nums，0，I)；

}

System.out.println("堆排序:")；

for (int k : nums) {

system . out . print(k+" ")；

}

}

/**

*堆调整，使其生成最大的堆

* @param nums

* @param i

* @param大小

*/

public void PerDown(int[]nums，int i，int size){

int left = 2 * I+1；

int right = 2 * I+2；

int max = I；

if(左& lt尺寸和尺寸。& ampnums[left]>nums[max]){

max =左侧；

}

if(右& lt尺寸和尺寸。& ampnums[right]>nums[max]){

max =右；

}

if(max！= i){

int temp = nums[I]；

nums[I]= nums[max]；

nums[max]= temp；

percDown(nums，max，size)；

}

}

总结

以下是七种经典排序算法指标的比较:

-结束-

定价:59.80元

书号:9787302501725