锐客网

  1. 首页 > it技术 > >

冒泡排序、插入排序、快速排序、堆排序、归并排序总结

排序在算法学习中占用很重要的地位，也很实用。就用这篇博客来总结一下常用的几种排序算法。
冒泡排序 【冒泡排序、插入排序、快速排序、堆排序、归并排序总结】在水中，大的泡泡会往上浮。
在冒泡排序中，通过不断交换两个相邻的数据，使大的（或小的）数字往数组头部移动。最终将数组全部排序。

冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
image.png 如上图所示
数组 [4,6,7,5]。我们将这个数组降序排列。
首先从数组最后一个数开始，依次与他前一个数比较，如果大于前一个数，交换。这样经过一轮循环。我们将最大的数放到了数组index=0的位置。
然后继续上述操作，将数组中第二大的元素移至index=1的位置。
依次下去，直到完成数组的排序。
代码

public class BubbleSort { public void sort(int[] src)throws Exception { if(src=https://www.it610.com/article/=null||src.length==0) throw new Exception("参数错误"); for(int i=1; i=i; j--) {//将第i大的数字方法正确的位置 if(src[j]>src[j-1]) swap(src,j,j-1); } } }private void swap(int[] src,int index_a,int index_b) { int temp=src[index_a]; src[index_a]=src[index_b]; src[index_b]=temp; }public static void main(String[] args) { BubbleSort bubbleSort=new BubbleSort(); int[] src= https://www.it610.com/article/{90,70,30,80,60,10,40,50,20}; try { bubbleSort.sort(src); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } for(int i=0; i

时间复杂度
最坏的情况，就是数组本来是升序的，要将其变为降序的。共需要进行1+2+3+。。。+n-1=n*（n-1）/2次比较和交换操作，时间复杂度是o(n^2)。没有额外使用空间来存储中间变量，空间复杂度是o(1)。最好的情况，数组已经是排序好的，只需要遍历一遍，时间复杂度是o(n)。
插入排序 如果你打扑克，并且喜欢将手里的牌按顺序排好，那么你一定会插入排序。
在插入排序中，我们维护一个有序数组，每来一个数字，我们将他插入到有序数组中，使该数组仍然有序。直到我们将所有的数字都插入到合适的位置。

冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
image.png
如上图所示，我们在数组前部维护一个有序序列，然后依次将数字插入到有序序列的适合位置，直到所有数字都插入到有序数列中。
代码
public class InsertSort { public void insertSort(int[] src)throws Exception { if(src=https://www.it610.com/article/=null||src.length==0) throw new Exception("参数错误"); int temp=0; int i,j; for(i=1; isrc[i-1]) { temp=src[i]; for(j=i-1; src[j]=0; j--) {//将第I个数组插入到合适的位置 src[j+1]=src[j]; } src[j+1]=temp; } } }public static void main(String[] args) { InsertSort insertSort=new InsertSort(); int[] src= https://www.it610.com/article/{90,70,30,80,60,10,40,50,20}; try { insertSort.insertSort(src); } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } for(int i=0; i

时间复杂度
在最坏的情况下，也就是数组本来是升序的，我们要把它变为降序的，共需要1+2+3+。。+n-1次比较和移动，时间复杂度是o(n^2)。最好情况下，数组本来就是排序好的，只需要遍历一遍就行，时间复杂度是o(n)
快速排序 快速排序的思想是从数组中取一个数，将这个数字放到适合的位置，使它前面的数字比它小（或者大），后面的数字比它大（或者小）。这样就将数组分为两个部分，然后依次对这两个子数组进行相同的操作，直到所有数组都在正确的位置。

冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
image.png
如上图所示，我们使用两个指针，一个指向数组最左，一个指向数组最右。将最左的数作为基准值。先拿基准值和右边指针指向的数组进行比较，如果基准值较小，交换两个指针的值。移动左边指针，再比较基准值和左边的指针指向的数字，重复操作。直到将基准值放到合适的位置上。这就将数组分成了两部分，然后再分为对这两部分做同样的操作，直到所有数组都在正确的位置上。
代码
public class QuickSort { public void quickSort(int[] src)throws Exception { if(src=https://www.it610.com/article/=null||src.length==0) throw new Exception("参数错误"); partition(src,0,src.length-1); }public void partition(int[] src,int start,int end) { if(start>=end) return; int key=src[start]; int i=start; int j=end; while(i=key) j--; if(i
时间复杂度
快速排序的递归中，数组形成了一个二叉树，快速排序的时间复杂度和二叉树的高度有关。在这个二叉树中，每一层的时间复杂度是n，树的高度与key值的选择有关。如果选择的key值恰好能将数组等分成两半，则树的高度是log(n)，如果key值只能将数组分成一份，则数的高度是n。所以，快速排序的时间复杂度最好是n*log(n)，最坏是n^2。
快速排序优化
如果key值取得不好，那快速排序的时间复杂度最坏可能是n^2。key值取恰好能将数组平分为最好。因此有对于key值得优化方法，如三数区中法（三个数中间值作为key值），和随机法（随机取key值）。

冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
快速排序最好情况，树的高度是log(n)，时间复杂度是n*log(n)
冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
快速排序最坏情况，树的高度是n，时间复杂度是n^2 堆排序 堆排序是基于堆这种数据结构的一种排序算法。
堆是一颗完全二叉树，堆有最大堆和最小堆。最大堆中每个父节点都比它的子结点大，最小堆中每个父节点都比它的子结点小。
因此，堆有以下的性质：
1.堆中根结点是最大值或者最小值。
2.将堆层序遍历的结果放入数组中（数组index从0开始），index=a的两个子结点是2a+1和2a+2
在了解了堆以后，我们来说以下堆排序。堆排序中，首先将数组元素构建成堆（最大堆和最小堆），然后将堆中根结点和堆中最后一个结点交换，重新构建堆。直到将所有的元素排序成功。

image.png
代码
public class HeapSort {public void headSort(int[] src)throws Exception { if(src=https://www.it610.com/article/=null||src.length==0) throw new Exception("参数错误"); for(int i=(src.length-2)/2; i>=0; i--) { heapAdjust(src,i,src.length-1); } for(int i=src.length-1; i>0; i--) { swap(src,0,i); heapAdjust(src,0,i-1); } }public void heapAdjust(int[] src,int start,int end) { int temp=src[start]; int j=start*2+1; for(j=start*2+1; j<=end; j=j*2+1) { if(j
时间复杂度
构建堆的时间复杂度是o(n)，第a次交换堆顶元素并重建堆的时间复杂度是log(a)，共需要交换n-1次。因此，时间复杂度是log(1)+log(2)+...+log(n-1)=nlog(n)。堆排序的时间复杂度对原始数组的排列不敏感，最好最坏平均的时间复杂度都是nlog(n)。
归并排序 快速排序，堆排序都用到了二叉树的高度是log(n)。归并排序也是如此。
假设原始数据长度为n，归并排序先将数据一分为2，长度分别是n/2。然后对子数组继续二分，直到每个数组长度为1。然后对数组两两进行归并和排序，直到恢复原始数据长度。如下图所示。

冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
image.png
上图中，首先对数据进行二分，直到子数组长度为1。然后对数组进行合并，排序，直到恢复原始数组长度。
代码
public class MergeSort { public void mergeSort(int[] src)throws Exception { if(src=https://www.it610.com/article/=null||src.length==0) throw new Exception("参数错误"); sort(src,0,src.length-1); }public void sort(int[] src,int start,int end) { if(start>=end) return; int mid=(start+end)/2; sort(src,start,mid); sort(src,mid+1,end); merge(src,start,mid,end); }public void merge(int[] src,int start,int mid,int end) { int[] temp=new int[end-start+1]; int index=0; int i=start; int j=mid+1; while(i<=mid&&j<=end) { if(src[i]<=src[j]) { temp[index]=src[i]; i++; index++; }else { temp[index]=src[j]; j++; index++; } } while(i<=mid) { temp[index]=src[i]; i++; index++; } while(j<=end) { temp[index]=src[j]; j++; index++; } for(index=0; index
时间复杂度
归并排序在分解数组的时候时间复杂度是1，在合并数组的时候，时间复杂度是n，并且合并的次数是log(n)，因此总的时间复杂度是nlog(n)。并且归并排事件复杂度序对原始数据不敏感，最好，最坏，平均事件复杂度都是nlog(n)。
几种排序算法分析 冒泡排序、插入排序、快速排序、堆排序、归并排序总结
文章图片
image.png

    推荐阅读


    上一篇：若相惜

    下一篇：《秘密花园》第十四章|《秘密花园》第十四章 一位小王爷