🍬个人主页：Yanni.—
🌈数据结构：Data Structure.
🎂C语言笔记：C Language Notes
🏀OJ题分享： Topic Sharing
目录
前言：
快速排序
思路分析
三值取中法
挖坑法
思路分析
编辑 代码实现
左右指针法
思路分析
编辑 代码实现
前后指针法
思路分析
代码实现
快速排序实现
冒泡排序
思路分析
代码实现
前言：
今天给大家带来快速排序，所谓快速，那肯定是时间复杂度更优化的排序，学会了这个排序，在校招的题目，学校的考试，自己对数据结构的理解会变得更好的！
快速排序
快速排序是一种高效的排序算法，其基本思想是通过将待排序的序列划分为左右两个子序列，其中左子序列的元素都小于右子序列的元素，再递归地对子序列进行排序，直到整个序列有序为止。
思路分析
1.选出一个基准值key（一般都是以第一位或者最后一位为准）。
2.将所有比key小的值放在左边，所有比key大的值放在右边。
3.这样就分为了左右两个区间。
4.再将左右两个区间重复1和2操作，依次分治下去，最后就排好序了。
要实现这样的思路有三种方法：挖坑法，左右指针法，前后指针法。
三值取中法
为了避免极端情况（比如序列为逆序或者顺序的情况），选出基准值key可以用三值取中法来进行选择，三值分别是首值，中间值，尾值。
从这三个值当中选择中等的值来作为我们的基准值key，可以增加时间效率。
int GetMidIndex(int* a, int left, int right)
{int mid = (right + left) >> 1;if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else {return left;}}//a[left]<a[mid]else {if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else {return right;}}
}挖坑法
思路分析
1.将选出的基准值key的位置作为一个坑（pivot）。
2.然后从最后一位开始遍历，找到比key小的值停下，将这个值放到坑里面，然后坑就到了新位置
3.再从第一位开始遍历，找到比key大的值停下，将这个值放在新的坑里面，坑又到了新的位置
4.依次反复进行直到前后遍历碰撞。
图解如下：
代码实现
int PartSort1(int* a, int left, int right)
{int Index = GetMidIndex(a,left, right);//这里是三数取中，会在下面讲解Swap(&a[left], &a[Index]);int begin = left;int end = right;int pivot = begin;int key = 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;}pivot = begin;a[pivot] = key;return pivot;
}左右指针法
思路分析
1.左指针begin，右指针end，利用这两个指针前后遍历分别找到比key大的值和比key小的值。
2.将两个值进行交换，再重复1的操作。
3.当begin=end时操作停止，最后将key值与begin位置的值进行交换，完成了排序。
图解如下：
代码实现
int PartSort2(int* a, int left, int right)
{int Index = GetMidIndex(a, left, right);Swap(&a[left], &a[Index]);int begin = left;int end = right;int key = begin;while (end > begin){while (end > begin && a[end] >= a[key]){end--;}while (end > begin && a[begin] <= a[key]){begin++;}Swap(&a[end], &a[begin]);}Swap(&a[begin], &a[key]);return begin;
}前后指针法
思路分析
1.前指针prev，后指针cur，让cur去找比key大的值，找到后prev向前移动一位（prev++），并且与cur位置的值进行交换。
2.重复执行1的操作，知道cur把所有的数据遍历完成。
3.最后将key值与prev位置的值进行交换，完成排序。
图解如下：
代码实现
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key]&&prev++ != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[key]);return prev;
}快速排序实现
利用分治思想，用递归算法来进行代码实现。
void QuickSort(int* a, int left, int right)
{if (left >= right)//递归条件{return;}int KeyIndex = PartSort1(a, left, right);//挖坑法//int KeyIndex = PartSort2(a, left, right);//左右指针法//int KeyIndex = PartSort3(a, left, right);//前后指针法if (KeyIndex - left - 1 > 10){QuickSort(a, left, KeyIndex - 1);}else {InsertSort(a + left, KeyIndex - 1 - left+1);//直接插入排序}if (right - KeyIndex - 1 > 10){QuickSort(a, KeyIndex + 1, right);}else {InsertSort(a + KeyIndex + 1, right - (KeyIndex + 1) + 1);//直接插入排序}
}冒泡排序
冒泡排序是交换排序的一种。
思路分析
1.将第一个数与第二个数比较，大者则交换顺序。
2.然后比较对象向后移动一位，继续上一步操作。
3.直到比较完成为止，这样最大的数就排到最后一位。
然后再重复上面的操作，最后所以的数都排好，这就是冒泡排序。
代码实现
这里的flag是优化了基础的冒泡排序，提高了时间效率。
利用flag判断每次轮回序列是否已经排序好，这样可以避免重复的排序。
void BubbleSort(int* a,int n)
{int end = n - 1;for (int j = 0; j < end; j++){int flag = 0;for (int i = 1; i <= end-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0){break;}}
}好啦，这就是今天学习的分享啦！看到希望大家的三连呀！
如果有不当之处，欢迎大佬指正！
)