冒泡排序与快速排序详解及优化

Excel表格快速排序，Ctrl + Shift + F4 #生活技巧# #数码产品使用技巧# #办公软件快捷键#

Hello，同志们，今天分享有关冒泡排序和快排的算法思想以及代码实现。

一、冒泡排序

1、冒泡排序是什么？
冒泡排序是一种相对稳定的排序算法，时间复杂度0（N*N ), 冒泡排序就是通过两两比较，（以升序为例），从开头比较，一个数与它后面的比较，如果比后面的小，不动，如果比后面的数大，把它俩交换，这样一次排序后最大的数就在最大下标处，每比完一轮，缩小比较范围，N个数比较，总的比较次数为N-1轮。

注意：每比完一轮，缩小比较范围！！！

2、代码优化：
如果数据本身就是有序的，而比较每次都拿出两个比较，看是否需要交换，总共要比N-1轮，每轮内部也会比较多次，第i轮需要比较（N-i)次，消耗较大；

在每轮比较中可以置一个ex 布尔变量为false；如果发生交换，置为true；
一轮比较下来，如果数据有序就不会发生交换，每轮比较完后判断ex的真假，为假说明没交换，直接退出，后面的比较也不用做了， 剩下几轮的比较也只是在浪费时间，空间而已，没有任何意义
这样可以提高代码的效率。

比较图示：

3、代码如下：
可以用两个for循环嵌套写；也可以用while循环来控制比较轮数，内嵌一个for循环来比较数据大小

void BubbleSort(int* a, int len) { for (size_t i = 0; i < len-1; i++)//外围控制总比较轮数 { bool ex = false; for (size_t j = 0;j<len-i-1; j++)//哪两个数据比较？ { if (a[j] > a[j + 1]) { ex = true; swap(a[j], a[j + 1]); } } if (ex == false) { break; } } } //while()嵌套for（）循环 void BuBBleSort(int* a, int len) { assert(a); int sq = len;//sq控制比较轮数 while (sq > 0) { bool ex = false; for (int j = 0; j < sq - 1; ++j) { if (a[j]>a[j + 1]) { swap(a[j], a[j + 1]); ex = true; } } if (ex == false) { break; } --sq; } }

二、快排算法&优化

1、快速排序是什么？

采用分治策略，一次排序后，将数据划分为两半，一半比某一个数小，另一半比某个数大。

*利用递归，完成对数组的排序。

2、实现快排有三种方法：
（1）左右指针法：
两个指针，指向数组下标，找一个定值，让其它数与它比较，在两个指针相遇之前，左边指针找比这个数大的，右边指针找比这个数小的，交换这两个指针指向的值；返回相遇下标值，这样将数据划分为两部分，然后对左半边进行quickSort，对右半边进行quickSort。
代码如下：

#include <iostream> #include <assert.h> using namespace std; int PartSort(int *a, int begin, int end)//左右指针法 { //int key = GetMid(a, begin, end);//选取数据的优化 int key = end; while (begin < end) { while (a[begin] <= a[key] && begin<end) { begin++; } while (a[end] >= a[key] && begin<end) { end--; } if (begin < end) { swap(a[begin], a[end]); } } swap(a[begin], a[key]); return begin; } void QuickSort(int* a, int start, int final) { assert(a); if (start < final) { int div = PartSort(a, start, final - 1); QuickSort(a, start, div); QuickSort(a, div + 1, final); } } int main() { int arr[] = { 3, 6, 8, 1, 7, 9, 5, 2,4 }; int len = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, len); for (int i = 0; i <len; i++) { printf("%d ", arr[i]); } printf("\n"); system("pause"); return 0; }

快排时间复杂度：0（n*logn)
最差情况：每次选取的数都是最小的或者最大的数，像冒泡排序一样，此时时间复杂度0（N*N)，出现几率较小，但是不排除这种可能性。
当数组是有序的时候，每次选出来的那个数就是最大或者最小的，此时最坏情况出现。
优化算法：三数取中
选取一个刚好不大不小的数来和其他数作比较，采用三数取中法 用这个下标对应数来做key(划分数据值）。
代码如下：

int GetMid(int *a,int left, int right) { int middle = ((left + right) >> 1); //int middle = left+((right-left)>>1); if (a[left] < a[middle]) { if (a[middle] < a[right]) { return middle; } else if (a[left]<a[right]) { return right; } else { return left; } } else { if (a[middle] > a[right]) { return middle; } else if (a[left] > a[right]) { return right; } else { return left; } } }

利用上面的函数，可以避免像取到的数最大或最小，导致快排发挥不了作用的情况。

（2）前后指针法

两个指针，一前一后指向数组数据，前面指针先走，cur起始位置0，prev起始位置-1。
如图：

代码实现如下：

int PartSort1(int *a, int left, int right) { int prev = left - 1; int cur = left; int key = a[right]; while (cur < right) { while (a[cur] <= key) { cur++; prev++; }//cur大 while (++cur < right) { if (a[cur] < key&&++prev!=cur) { swap(a[cur], a[prev]); } } } swap(a[++prev], a[right]); return prev; }

（3）挖坑法

左右指针轮流做坑，记录key=a[right]最后一个数据的值，如果左指针找到比右指针大的，右边的相当于一个坑，让左指针指向的值覆盖右指针指向的值，此时左边就相当于一个坑，然后再在右边找比key小的数，覆盖左指针，循环寻找，最后剩下的这个坑里填的就是key。

如图：

代码如下：

int PitSort(int* a, int left, int right)//left和right轮流做坑 { int key = a[right]; while (left < right) { while (a[left] <= key&&left<right) { ++left; } a[right] = a[left]; while (a[right] >= key&&left < right) { --right; } a[left] = a[right]; } a[left] = key; return left; }

好了，今天的冒泡排序和快速排序就分享到这里啦，冒泡排序是一种稳定的算法，快排一般情况下效率较高，但是不稳定，在排序过程中，知道什么数据和什么数据相比较非常重要，路漫漫其修远兮，吾将上下而求索。
加油！Have a nice day~

网址：冒泡排序与快速排序详解及优化 https://www.yuejiaxmz.com/news/view/1280655

相关内容

快速排序详解
汇编语言冒泡法排序——使用子程序解决
python冒泡排序法实现的2种方法以及从大到小排序的实现
排序算法解析
Python 快速排序
洗碗机排水冒泡的原因及解决方法（有效应对洗碗机排水冒泡问题）
常见排序算法的性能以及应用场景
快速排序(代码通俗易懂，干净整洁)
c语言常见排序算法
排序算法与二分查找

随便看看