[C语言]排序的大乱炖——喵喵的成长记

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

前言

小喵喵课堂开课来，今天我们学习七个常见的排序，哦哦耶！！！

喵喵今天也要加油哦！

来吧，不乱叫，上导图：

前言

八大经典排序的概述

直接插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序(快排）

归并排序

总结

┗|｀O′|┛ 嗷~~，怎么能忘了基数排序呢？补上补上：

八大经典排序的概述

八大排序算法是指常见的八种经典排序算法，它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。

冒泡排序：比较相邻的元素，如果顺序错误就交换它们，重复这个过程直到整个数组有序。
选择排序：每次从待排序的数组中选择最小（或最大）的元素放在已排序数组的末尾，直到整个数组有序。
插入排序：遍历数组，将当前元素插入已排好序的子数组中的适当位置，直到整个数组有序。
希尔排序：通过设置间隔将数组分组，对每个分组进行插入排序，逐渐减小间隔，直到间隔为1时进行最后一次插入排序。
归并排序：采用分治的思想，将待排序数组划分为较小的子数组，然后递归地对子数组进行排序，并将排好序的子数组合并成更大的有序数组。
快速排序：选取一个基准元素，将数组划分为左右两部分，左边部分都比基准元素小，右边部分都比基准元素大，在递归地对左右两部分进行快速排序。
堆排序：将待排序数组构建成一个大顶堆，然后将堆顶元素与最后一个元素交换并重新调整堆，重复这个过程直到整个数组有序。
基数排序：根据元素的每个位上的值进行排序，先按低位排序，再按高位排序，直到所有位都排序完成。

直接插入排序

直接插入的排序规则，如图所示：

将end和tmp代入进去思考，一来的3，就算起始点，排好了位置，作为end,然后tmp是44，44>3，tmp>end,所以不交换位置，算排好了，end+1，tmp+1。那么第二次比较，end是44，tmp是38，end>tmp，交换位置，38排在44前面。那么第三次比较，5比44小，比38小，排在38前面。以此类推，循环排好数组。

void InSert(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

希尔排序

希尔排序是直接插入排序的升级版，先对数组进行有规律的分组，分成多个组，然后每个小组进行直接插入排序。每个小组排完后，再进行一次直接插入排序，就要轻松地多，能够快速排好，大大提高了排序的效率。

分成绿，蓝，红三组，分别进行直接插入排序。

void InsertSort(int* a, int n) 
{int gap = 3;for (j=0;j<gap;j++){for (int i = j; i < n-gap; i+=gap){int end = i;int tmp = a[i+gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end-=gap;}else{break;}}a[end + gap] = tmp;}}}

void InsertSort(int* a, int n) 
{int gap = n;int j = 0;while (gap > 1){gap = gap / 2;for (j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}}

选择排序

选择排序，很直观就是要选择，我们先选择3作为有序数组，然后从3后面的数组中选出最小的数，并于3进行比较，谁小谁站在前面。2比3小，2与3交换位置。依次往后推，拍成有序数组。

喵，很难评，这是简单版的一个点移动，而我们一般上的是困难版的两个点，喵，不好理解，喵喵，也是搞了好久，才明白滴，喵。那么让我们开始吧！猫猫队，冲冲冲！

两个点的移动（建议结合代码，自己也跟着走一走，感觉不就来了嘛！）：

//这是两个点的移动
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);// 如果left和maxi重叠，交换后修正一下if (left == maxi){maxi = mini;}Swap(&a[right], &a[maxi]);++left;--right;}
}

堆排序

就是以层序的方式从下往上，从大到小的排。升序建大堆，降序建小堆。

// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 自己先实现 -- O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}

冒泡排序

冒泡排序，好理解，教学意义重大。简单的来说就是从一端开始，两两交换，把小的换在前面去就OK了！
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false){break;}}
}

快速排序(快排）

快排有很多种方法，比如hoare法，挖坑法，前后指针法：

1.hoare法：

无言，如图所示

int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
int PartSort1(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi])--right;// 左边找大while (left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;return keyi;
}

挖坑法：

int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
int PartSort2(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);// 21:10继续int key = a[left];int hole = left;while (left < right){// 右边找小while (left < right && a[right] >= key)--right;a[hole] = a[right];hole = right;// 左边找大while (left < right && a[left] <= key)++left;a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

前后指针法：

int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
int PartSort3(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

归并排序（递归）：

int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
int PartSort3(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort3(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}