编辑
哈喽大家好，我是保护小周ღ，本期为大家带来的是常见排序算法中的交换排序，主要有冒泡排序，快速排序，快排分享了三种算法：挖坑法，左右指针法，前后指针法，以及两种优化方式：解决快排最坏情况的“三数取中”，避免递归次数过多的"小区间优化"，包您一看就会，快来试试吧~
编辑
编辑
目录
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位 置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移 动。
1.交换排序——冒泡排序
冒泡排序（Bubble Sort）基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。直观表达，每一趟遍历，将一个最大的数移到序列末尾。也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，将他们之间小的，或者大的值交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
1.1 算法思想
比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第i个和第i+1个比较与交换，随后第i+1个和第i+2个一对比较交换，这样直到倒数第n-1个和最后n个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位
……
1.2 动图演示
编辑
算法实现：
Swap(int*p1, int*p2) { inttmp=*p1; *p1=*p2; *p2=tmp; } voidPrint(int*a) { for (inti=0;i<N;i++) { printf("%d ",a[i]); } } voidBubbleSort(int*a, intn) { for (intj=0;j<n;++j) { intsize=0; for (inti=1;i<N-j;++i) { if (a[i-1]>a[i]) { Swap(&a[i-1],&a[i]); size=1; } } if (size==0) { break; } } } intmain() { inta[N] = {0}; for (inti=0;i<N;++i) { a[i] =rand(); } BubbleSort(a,N); Print(a); return0; }
编辑
其中有一段优化程序，是定义一个变量判断排序是否在做无效操作，当内循环处于交换状态时，则数据未排序完毕，否则视为，数据已有序，我们就可以break;中止掉程序，避免做无用遍历。
1.3 冒泡最好的情况
待排序数列有序时，时间复杂度是O(N)。外循环只执行一次，内循环N-1,N-2,N-3……
1.2 冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
总结：
总的来说，冒泡排序是一种可以的排序，比直接选择排序要好，虽然有优化程序，但是，整体算法效率跟其他排序来比，还是差一些，比较适合新手学习。
2. 交换排序——快速排序
快速排序(Quicksort)是Hoare于1962年提出的一种二叉树结构的交换排序方法，有时候也叫做划分交换排序，是一个高效的算法，其基本思想为：任取待排序 元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有 元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所 有元素都排列在相应位置上为止。这是一个分治算法，而且它就在原地交换数据排序。
编辑
是目前已知最快的排序算法，会比一般的排序更节省时间。
2.1 快速排序——挖坑法
编辑
编辑 算算法实现：
//打印voidPrint(int*a,intn) { for (inti=0;i<n;++i) { printf("%d ",a[i]); } } //挖坑法voidQuickSort(int*a,intleft,intright)//升序{ if (left<right) { intbegin=left; intend=right; intpivot=begin;//记录坑位的下标intkey=a[begin];//坑值while (begin<end) { //右边找小，放到左边while (begin<end&&a[end] >=key)//与坑值比较 { --end; } //小的放在左边的坑里，自己形成了新的坑位a[pivot] =a[end]; pivot=end; //左边找大，放在右边while (begin<end&&a[begin] <=key)//与坑值比较 { ++begin; } //大的放在右边的坑里，自己形成了新的坑位a[pivot] =a[begin]; pivot=begin; } //最后将坑值给到坑位a[pivot] =key; //[left,right]//[left,pivot-1] [pivot+1,right]//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归QuickSort(a, left, pivot-1); QuickSort(a, pivot+1, right); } else { return; } } intmain() { inta[10] = {0,9,5,6,3,2,1,7,8,4}; //挖坑法QuickSort(a,0,sizeof(a)/sizeof(a[0])-1); //打印Print(a,sizeof(a) /sizeof(a[0])); return0; }
编辑
快排的缺点
根据上面的代码，我们来分析一下快排的缺点：
编辑
如何解决快排对有序数据排序效率很差的方法？
三数取中法
编辑
所谓三数取中，不是取最大值，最小值，以及他们的中间值，而是取左边（begin）、右边（end）和中间（begin+end）/2;
在有序的情况下中间的值刚好就是二分，将取出的值作为坑位，就不会出现最差的这种情况。我们依旧使用区间的开头作为“坑值”，但是要使用三数取中的逻辑。
选坑位：
intbegin=left; intend=right; //使用三数取中选“坑值”，用mid存储其下标intmid=GetMidIndex(a, begin, end); //将区间首值当作坑位//坑值与首值交换，避免算法混乱//一般我们会将区间首值作为坑值Swap(&a[begin], &a[mid]);//传地址调用//存储坑值intkey=a[begin];
三数取中 GetMidIndex();
intGetMidIndex(int*a,intleft,intright) { //二分intmid= (right-left) /2; if (a[left]<a[mid]) { if (a[left]<a[right]) { if (a[mid]<a[right]) { returnmid; } else//a[mid]>=a[right] { returnright; } } else//a[left]>=a[right] { returnleft; } } else//a[left]>=a[mid] { if (a[mid]<a[right]) { if (a[left]<a[right]) { returnleft; } else//a[left]>=a[right] { returnright; } } else//a[mid]>=a[right] { returnmid; } } }
交换Swap()；
//交换voidSwap(int*p1, int*p2) { inttmp=*p1; *p1=*p2; *p2=tmp; }
经过三数取中的处理，就不会出现快排的最坏情况，但也几乎不会成为最好的情况，有利有弊，我们在面试的过程中只需要写基础版的快排即可，以防时间不够。
小区间优化：
关于如果处理数据多，相应的递归次数多，会不会影响操作快排的性能？
编辑
当我们在使用快排对大量数据进行排序时，我们可以采用小区间优化，减少递归次数，达到优化程序得到目的。
对当待处理数据大于10的子序列进行快排递归。
对当待处理数据低于10的子序列进行直接插入排序进行排序，避免递归次数过多。
这个10不是固定的，可以根据处理的数据量调整。
//区间[left,right]//左区间[left,pivot-1] 右区间[pivot+1,right]//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归// 小区间优化if (pivot-1-left>10)//对当待处理数据大于于10的子序列进行快排递归排序{ //快排QuickSort(a,left,pivot-1); } else{ //采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如：区间[0,9]实际上有10个数} if (right- (pivot+1) >10) { QuickSort(a,pivot+1,right); } else{ InsertSort(a+pivot+1, right-(pivot+1)+1); }
如果大家有想了解直接插入排序可以查看博主的另一篇：
常见排序算法之插入排序——直接插入排序、希尔排序：http://t.csdn.cn/X2mlq
2.3 快速排序——左右指针法
编辑
根据上图的示例我们应该能够理解左右指针法是什么样的逻辑，跟挖坑法是一样的思想，单趟排序完毕实现左边比坑位小，右边比坑位大。但是即使左右指针法跟挖坑法的思想是一样的，但是他们单趟的运算结果是不一样的。
编辑
算法实现：
voidQuickSort(int*a, intleft, intright) { if (left<right) { intbegin=left; intend=right; //选坑位intmid=GetMidIndex(a, begin, end);//三数取中Swap(&a[begin], &a[mid]); intkey=begin; while (begin<end) { while (begin<end&&a[end] <=a[key]) --end; while (begin<end&&a[begin] >=a[key]) ++begin; Swap(&a[begin], &a[end]); } Swap(&a[begin], &a[key]); //分治递归QuickSort(a, left, begin-1); QuickSort(a, begin+1, right); } }
2.4 前后指针法
- 采用perv记录区间第一个元素的下标，采用cur记录区间第二个元素的下标。
- cur找小，每次遇到比key(坑值)小的值就停下来，++prev。
- 交换prev和cur位置的值
编辑
算法实现：
//左右指针法voidQuickSort(int*a, intleft, intright) { if (left<right) { //选坑位intmid=GetMidIndex(a, left,right);//三数取中Swap(&a[left], &a[mid]); intkey=left; //初始化指向intprev=left, cur=left+1; while (cur<=right) { if (a[cur] <=a[key])//&&++prev!=cur { ++prev; //避免无效操作if(cur!=prev) Swap(&a[prev],&a[cur]); } ++cur; } Swap(&a[key], &a[prev]); //分治递归QuickSort(a, left, prev-1); QuickSort(a, prev+1, right); } }
快速排序的特性总结：
1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2.时间复杂度：O(N*logN)
3.空间复杂度：O(logN)
4.稳定性：不稳定
总结：
快排是我们一定要掌握的一种排序算法，在面试、笔试中也是很常见的，博主分享的三种方法：挖坑法，左右指针法，前后指针法，只少要掌握一种，但是要其他的方法也要知道算法思想。还有两种优化方式，小区间优化和三数取中，也要知道是什么逻辑，解决什么问题。
编辑
感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ *★,°*:.☆(￣▽￣)/$:*.°★*
文章存在借鉴，如有侵权请联系修改删除！
