数据结构——排序（续集）

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥
✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨

上一篇博客我们说到了四种排序算法数据结构——排序，这一篇博客我们继续在排序算法里面遨游~体会更多的排序算法的魅力~

交换排序

冒泡排序

基本思想

代码

时间复杂度

快速排序

基本思想

Hoare版本找基准值

挖坑法找基准值

lomuto前后指针找基准值

快速排序特性总结

归并排序

基本思想

代码

时间复杂度

交换排序

》交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

》交换排序的特点是：将键值较大的记录向序列的尾部移动，键值小的记录向序列的前部移动

交换排序包括两种，一种是冒泡排序，一种是快速排序，我们一个个来看看~

冒泡排序

基本思想

冒泡排序是⼀种最基础的交换排序。因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动，所以叫做冒泡排序。

它的基本思想是根据元素个数来比较不同趟数，每一趟里面元素两两比较，如果满足一定的条件就进行交换，最终最大的（或者最小的）元素会到最后面 ~

这里举一个简单的例子：

现在我们想要排序【3，5，9，7，2】这个数组排成升序~

第一趟比较：

【3，5，9，7，2】——>【3，5，9，7，2】——>【3，5，7，9，2】——>【3，5，7，2，9】

第二趟比较：（最后一个元素已经是最大的了，排序剩下的元素）

【3，5，7，2，9】——>【3，5，7，2，9】——>【3，5，2，7，9】

第三趟比较：

【3，5，2，7，9】——>【3，2，5，7，9】

第四趟比较：

【2，3，5，7，9】

经过四趟的排序，我们的数组就已经成为了升序~

代码

通过前面的思路，我们可以写出下面的代码：

//冒泡排序
void BubbleSort(int* arr, int sz)
{//外层循环比较趟数for (int j = 0; j < sz - 1; j++){//内层循环元素两两比较for (int i = 0; i < sz - 1 - j; i++){//前面元素比后面大就交换if (arr[i] > arr[i + 1]){int tmp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = tmp;}}}
}

排序成功~

时间复杂度

按照上面的代码，第一趟比较次数为n-1，第二趟比较次数为n-2……第n-2趟比较次数为2，第n-1趟比较次数为1，是一个等差数列（n-1+1)(n-1)/2,根据时间复杂度的规则也就是O（N^2),事实上，上面的代码我们也可以给它做出优化~如果数组有序，那么第一趟就不会进行交换，我们可以标记一下~后面就不需要继续比较了~

优化代码：


//优化的冒泡排序
void BubbleSort(int* arr, int sz)
{//外层循环比较趟数for (int j = 0; j < sz - 1; j++){int flag = 1;//标记当前数组是否有序//内层循环元素两两比较for (int i = 0; i < sz - 1 - j; i++){//前面元素比后面大就交换if (arr[i] > arr[i + 1]){//进行了交换，说明数组无序flag = 0;int tmp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = tmp;}}if (flag == 1){break;//数组有序，不需要继续比较}}
}

排序成功~这样如果是一个有序的数组，时间复杂度就会降低，最好的情况是第一趟就发现有序，那么时间复杂度为O（N），如果本来就是无序的，时间复杂度依然是O（N^2)

现在我们来比较一下排序100000个数据的运行时间~

我们可以看到冒泡排序达到了二十几秒，所以我们排序中是不推荐使用的~

快速排序

基本思想

》快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

》基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（这样就可以把基准值放到它该放的位置上），然后再分左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

Hoare版本找基准值

这里找基准值有很多的版本，首先来看看 Hoare版本，思路如下：

》 right 从右往左找比基准值要小的数据

》 left 从左往右找比基准值要大的数据

》找到之后， left 和 right 交换
》当 left > right ，基准值 key 和 right 交换

我们结合一个例子画图理解一下：

首先让基准值key就是left，left++往后面走一个，right指向最后一个元素

right 从右往左找比基准值要小的数据

left 从左往右找比基准值要大的数据

找到了就交换下标为left和right的数据

再次重复前面的步骤，直到left>right

right 从右往左找比基准值要小的数据

left 从左往右找比基准值要大的数据

left>right,基准值 key和 right 交换

我们可以看到基准值放到了它应该放的位置，前面的元素都比它小，后面的元素都比它大。

然后再把左右序列进行类似的操作~

这个排序的过程事实上就是不断二分的过程，不断地分成左右子序列，接下来看看代码

//Hoare版本找基准值
int _QuickSort(int* arr, int left, int right)
{int keyi = left;//记录基准值下标left++;while (left <= right){//每一个循环都写left <= right，确保不越界// right 从右往左 找比基准值要小的数据while (left <= right && arr[right] > arr[keyi]){right--;}// left 从左往右 找比基准值要大的数据while (left <= right && arr[left] < arr[keyi]){left++;}//找到了，交换if (left <= right){Swap(&arr[left], &arr[right]);//交换后继续找直到left>rightleft++;right--;}}Swap(&arr[keyi], &arr[right]);return right;
}//快速排序
void QuickSort(int* arr, int left, int right)
{//找基准值int key = _QuickSort(arr, left, right);//左右子序列重复操作//[left,key-1]   [key+1,right]if (left < key - 1){//需要判断，避免越界！！！QuickSort(arr, left, key - 1);}if (key + 1 < right){//需要判断，避免越界！！！QuickSort(arr, key + 1, right);}
}

注意点：

》我们是right 从右往左找比基准值要小的数据，left 从左往右找比基准值要大的数据，但是在我们的代码实现中，找到与基准值相等的也算进去进行交换了，这样可以更好地实现二分的目的，提高代码效率~

》最后递归要判断下标是否有效

以上面代码的例子为例：

如果我们的key就是最大的，left走到最后面，那么right也就是key，是数组的最大下标，那么key+1=10就会越界【10，9】这就不是有效的

时间复杂度：

我们知道递归的时间复杂度=递归的次数*一次递归的时间复杂度

因为不断地进行二分，我们认为递归的次数为logN（如果数组所有元素相等或者已经有序，那么递归的次数为N，这种情况很少~），一次递归时间复杂度O（N）——这里虽然看起来是两层循环，但是里面的一层循环，只是用来判断，并没有完全的遍历数组~

所以时间复杂度为O（N*logN）

比较时间：

我们可以看到快速排序效率还是很高的~

挖坑法找基准值

这里快速排序也是使用递归来实现，但是找基准值方法不一样，我们一起来看看~

》创建左右指针left、right，首先 right 从右向左找出比基准值小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"

》然后 left 从左向右找出比基准值大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"

》结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）

我们依然画图理解~

3比基准值小，把它拿到原来的坑位，right成为新的坑位

left找比基准值大的7，找到了，7去填坑

现在的left成为新坑

right继续找，如果相遇就停下来~

arr【hole】=key；返回坑hole就是基准值下标

代码：

//挖坑法找基准值
int _QuickSort2(int* arr, int left, int right)
{int hole = left;int key = arr[hole];//保存最开始坑位值,也就是基准值while (left < right){// right 从右向左找出比基准值小的数据// 找到后立即放入左边坑中，当前位置变为新的"坑"//这里相等就继续遍历while (left<right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;// left 从左向右找出比基准值大的数据// 找到后立即放入右边坑中，当前位置变为新的"坑"while (left<right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}//相遇或者left>right跳出循环arr[hole] = key;return hole;//返回坑位
}

排序成功~

注意点：

》这里相等也继续找

例：（一方面，如果里面元素相同，那么不断的交换也就降低了效率~）

另外一方面，同时以代码里面的数组为例

{ 9,1,2,5,7,4,8,6,3,5 }

第一轮：

left最开始就是hole的位置，arr【left】=key，那么就会不停的与自己进行交换，成为新坑位，不会往后面走，这就出现问题了~死循环了~

有的人可能会说left++不就可以了吗？

我们依然使用上面的数组验证~

这个时候我们就发现坑位一直在俩个位置变化，没有改变~因为依然有相同的元素，所以left++也不能解决这个问题~

接下来我们看看left能不能++呢？

》这就是另外一个注意点：left不能++

我们依然使用上面的数组验证~

这就分左右序列了，我们先来看看左边的序列

我们继续来看看它的左边的序列

我们发现left和right已经相遇了，那么就不会去填坑了~所以left不能++

所以写代码的时候还是需要多多注意这些问题~

时间复杂度依然为O（N*logN）

lomuto前后指针找基准值

基本思想：创建前后指针，从左往右找比基准值小的进行交换，使得小于基准值的都排在基准值的左边

思路：

我们依然画图理解

1比6小，++prev，prev与cur数据交换（这里++prev 等于 cur可以不进行交换），++cur

2比6小，++prev，prev与cur数据交换（这里++prev 等于 cur可以不进行交换），++cur

7比6大，位置不变，++cur

9比6大，位置不变，++cur

3比6小，++prev，prev与cur数据交换，++cur

cur已经越界，交换key和prev位置数据，返回prev就是基准值下标，这样小于基准值6的都排在基准值6的左边

有了前面的画图，相信这里的代码就不是什么大问题了~

代码：


//lomuto前后指针找基准值
int _QuickSort3(int* arr, int left, int right)
{int key = left;//当前基准值下标int prev = left, cur = left + 1;//cur探路while (cur <= right)//确保下标不越界{//比基准值小，++prev如果不等于cur，交换prev和cur位置数据,cur++if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[prev], &arr[cur]);cur++;}//比基准值大else{cur++;}}//cur已经越界，交换key和prev位置数据，返回prev就是基准值下标Swap(&arr[key], &arr[prev]);return prev;
}

排序成功~

快速排序特性总结

1. 时间复杂度： O(N * logN)

2. 空间复杂度： O(logN)

归并排序

基本思想

》归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法 ,该算法是采用分治法（Divide and Conquer）的⼀个典型应用。

》将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成⼀个有序表，称为二路归并。

比如下面的例子：

不断地二分最终得到每个子序列只有一个元素（只有一个元素肯定是有序的），然后合并序列成为有序的序列~这里毫无疑问就需要使用到递归了！我们来写写代码~

代码


//归并排序
//合并序列成有序的序列，需要一个临时数组来保存
void _MergeSort(int* arr, int left, int right, int* tmp)
{//相等说明只有一个元素，直接返回if (left >= right){return;}//分成子序列int mid = left + (right - left) / 2;//这种写法好处是避免数据过大引起存储不了//【left，mid】  【mid+1，right】_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并左右有序子序列int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//保存数组的下标//合并while (begin1 <= end1 && begin2 <= end2){//前面序列元素小，就放到tmp数组中if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];//别忘记下标往后面走}else{tmp[index++] = arr[begin2++];//别忘记下标往后面走}}//已经跳出循环，说明越界了// 处理还有剩余元素的情况while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//将排序好的tmp给arrfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}//归并排序
void MergeSort(int* arr,int sz)
{//开辟一块空间存排序的数组int* tmp = (int*)malloc(sizeof(int) * sz);if (tmp == NULL){perror("malloc fail");exit(1);}//调用排序方法_MergeSort(arr, 0, sz - 1, tmp);//动态申请的空间一定要释放,并且及时置为空free(tmp);tmp = NULL;
}