排序算法：(从小到大进行排序)
目录：
1、冒泡排序法：
冒泡排序法是最基本的排序算法，通过比较数组中相邻两个数的大小，如果右侧比左侧小则交换二者的位置，否则不动，假设有如下的数组：
?那么，我们从第一个数和第二个数开始进行比较，因为左侧的数大于右侧的数，故二者做交换，交换后，我们比较第二个数和第三个数
因为左侧的数小于右侧的数，故不发生变化，依次向后比较，最后比较的是第8个数和第9个数，最终该数组中最大的数被我们移到了右侧，换而言之这个数已经来到了正确的位置上，第一趟的排序过程如下：
接下来，我们要进行n-1次这样的排列过程(最后只剩下一个元素的时候无需排列)，便能完成最终的排序，由此可知，对于n个数来说，最坏的情况共需要排列n-1趟，那么对于这种算法来说，其时间复杂度是：
实际上我们可以对冒泡排序做一定的优化，假设在某一趟遍历中我们发现，没有出现交换的情况，也就是说此时数组已经是有序的，那么我们便没有必要继续遍历下去了，所以，实际上对于最好的的情况，也就是数组本身就是有序的，冒泡排序只需要进行n-1次比较即可，时间复杂度为O(n)，最终代码实现如下：
#include <stdio.h>
int main() {
int arr[] = { 5,2,4,3,9,8,7,2,2,2 };
int len = sizeof(arr) / sizeof(int);
BubbleSort(arr, len);
}
void BubbleSort(int* arr, int len) {
for (int i = 1; i < len - 1; i++) {
int flag = 0;// 标志位——检测是否此时的数组已经成为有序数组
for (int j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
// 俩俩相邻比较
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = 1;
}
}
if (flag == 0) return;// 已经成为有序数组，无需再排列跳出即可
}
return;
}2、选择排序法：
选择排序和冒泡排序的方法十分相近，其目的都是找到当前遍历的数组中的最值，并用它和端点值进行比较，如果不同的话则一定时比端点值大，因此交换二者的位置，反之如果二者不相等，要么是比端点大，要么是相等，假设有如下数组：
假设我们此时要进行从小到大的排序，那么我们令右侧为端点，那么首先我们需要找到从头到端点内的最大值，显然最大值是9，由于9比端点值6要大，故做交换，排序过程如下：
对于选择排序而言，其最大的优点在于，交换移动的次数很少，最多进行n-1次，但是无论对于最好的情况还是最差的情况，其需要进行比较的次数是一致的，故其时间复杂度为：
最终我们的代码实现如下：?
#include <stdio.h>
void SelctSort(int* arr, int len);
int main() {
int arr[] = { 5,2,4,3,9,8,7,2,2,2 };
int len = sizeof(arr) / sizeof(int);
SelctSort(arr, len);
}
void SelctSort(int* arr, int len) {
for (int i = 0; i < len; i++) {
// 循环遍历当前列，找到最值
for (int j = i + 1; j < len; j++) {
// 最值与端值作比较
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return;
}3、插入排序：
插入排序的思想是把数组分为了有序列和无序列两部分，那么我们首先将数组分为有序组和无序组两部分，假如一个数组中只有一个元素，那么该数组本身就是有序的，故我们设第一个元素构成的数组为有序组，而其余部分为无序组，那么我们从无序组中取出首元素，将其插入在有序组的合适的位置即可，那么假设我们有如下数组：
那么此时我们取出无序组中的首元素，也就是1，和有序组的首元素进行比较，我们发现1>4,故我们需要把1的位置向前移动，为了不过与频繁的交换数组中的元素，故我们换一种方式方式完成移动，也就是在有序组向前遍历的过程中，如果需要继续移动的话，则把后面的值覆盖为当前值，假设此时的数组如下所示：
那么我们取出无序组首元素6，用一个中间变量将其保存起来，接着将其与有序组中的元素从后向前依次比较，6<7，则说明6应该在7的前面，故我们令原来6的位置赋值为7，如下所示：
接着，继续用6和5比较，因为5<6故不用继续比较去了，将此时遍历到的有序组的元素的后一个值赋值为中间变量所保存的值，如下所示：
?那么此时我们的无序组首元素6来到了正确的位置上了，并且前五个元素也构成了一个新的有序列，最终的代码实现如下：
#include <stdio.h>
void InsertSort(int* arr, int len);
int main(){
int arr[] = { 5,2,3,7,9,6,1,7,2 };
int len = sizeof(arr) / sizeof(int);
InsertSort(arr, len);
}
void InsertSort(int* arr, int len) {
for (int i = 1; i < len; i++) {
int j = 0;
int temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}4、希尔排序
希尔排序是一种特殊的插入排序，希尔排序会在开始做预排序，先分组，进行组内排序，直到分的组中包含全部元素后，进行一次插入排序，假设我们的数组如下：
首先，我们需要确定一个增量，这个增量决定我们隔几个元素取一个元素并放在一组里，通常我们取数组长度的一半作为增量的初始值，增量每次折半，那么对于该数组而言，增量初始值应该为4，也就是分为如下几组：
我们进行组内排序，以插入排序的方法进行，结果如下：
接下来增量除以二，再次分组，分组及结果如下：
直到增量变为1，我们进行的就是原本的插入排序，其好处在于，我们最后一次的插入排序在进行比较的过程中不会超过3次，故在数据量较大的情况下，希尔排序的效率会更高一些
实现代码如下：
#include <stdio.h>
int main() {
int arr[] = { 5,2,4,3,9,8,7,2,2,2 };
int len = sizeof(arr) / sizeof(int);
ShellSort(arr, len);
}
void ShellSort(int* arr, int len) {
for (int Increment = len / 2; Increment > 0; Increment /= 2) { // 确定增量控制主循环
for (int i = 0; i < Increment; i++) { //确定当前增量下，共有多少组需要排列
// 当前增量下的单组排序
for (int j = i + Increment; j < len; j += Increment) {
int temp = arr[j];// 确定无序组的首元素
int k = j - Increment;// 确定有序组的末尾元素
while (arr[k] > temp && k >= 0) {
arr[k + Increment] = arr[k];
k -= Increment;
}
arr[k + Increment] = temp;
}
}
}
return;
}5、计数排序(桶排序)
计数排序也叫做桶排序，我们申请一个新的数组bucket作为容器，我们利用bucket的下标代表待排序数组的数，而bucket中存数组中不同数字的个数，假设有如下数组：
?首先我们要确定数组中的最大值，从而知道我们要获取一个多大的容器，假设最大值为max，那么我们的bucket数组则要申请max+1的空间用来存放数据，那么根据上述数组，我们的bucket中应该有8个int大小的空间，通过遍历待排序数组的值，在bucket中存放其下标所对应的数字在待排序组中出现的次数，如下所示：
?那么我们只要对bucket数组从小到达进行遍历输出，输出的次数取决于bucket中对应元素的值，代码实现如下：
#include <stdio.h>
void BucketSort(int* arr, int len);
int main() {
int arr[] = { 5,2,4,3,9,8,7,2,2,2 };
int len = sizeof(arr) / sizeof(int);
BucketSort(arr, len);
}
void BucketSort(int* arr, int len) {
int max = arr[0];
for (int i = 0; i < len; i++) {
if (arr[i] > max) max = arr[i];
}
int* buf = (int*)malloc(sizeof(int) * (max + 1));
assert(buf != NULL);
for (int i = 0; i <= max; i++) buf[i] = 0;
for (int i = 0; i < len; i++) {
buf[arr[i]]++;
}
for (int i = 0; i <= max; i++) {
while (buf[i] != 0) {
printf("%d ", i);
buf[i]--;
}
}
printf("\n");
free(buf);
}6、堆排序
堆排序主要是利用了“堆”这一结构的性质，堆分为大顶堆和小顶堆，对于大顶堆而言，对于每一个父节点均大于其子节点，反之则是小顶堆，因此我们如果想要将进行堆排序的话，首先要进行堆的构建，首先我们需要先将原始数据整理为堆的形式，假设有如下的数组：
将其写作堆的形式，如下：
此时，我们虽然将数组写作了堆的结构，但是每个元素的下标是不变的，因此这就需要我们建立堆的结构和数组下标的联系，由于，我们要从最后一个父节点开始遍历，那么首要目的就是先找到最后一个父节点是谁，我们可以通过结点数除以2减1的方式获取最后一个父节点的下标，也就是数组中元素的个数除以2减1，那么接着我们为了确定父节点和子节点的大小关系，我们要找到父节点和子节点的下标关系，才能进行判断，那么通过观察我们可以发先，假设我们正在遍历的父节点下标为i，那么其左子结点为2*i+1，而右子节点则为2*i+2，这样我们就确定了数组下标和堆结构的关联了；
如下的堆结构所示我们最后一个父节点的下标为3，因此我们要开始判断其和子节点之间的关系：
由于，下标为3的元素含有两个子节点，子节点下标分别为7和8，其中最大的子节点是下标为8的子节点值为6大于我们的父节点，故需要交换下标为3和8的元素的位置，变化后的堆结构如下所示：
接下来，该判断上一个父节点，也就是下标为2的元素：
那么我们判断的方式和上面一样，依旧是将最大的子节点和父节点做位置调换，变化的结构如下所示：
?接下来我们该判断的下一个父节点应该是下标为1的结点，由于1的两个子节点中更大的是3号结点，故将1结点和3结点做交换，如下图所示：
但此时我们发现由于交换了1和3结点的元素，而原本3结点也是父节点，此时3结点的子节点不满足，所有父节点都大于自己子节点的条件了，故我们需要对3结点重新做调整，其子节点7和8中更大的是8结点，故和3结点做交换，如下图所示：
因此，我们要做的就是每次遍历到一个新的父节点时，先判断其是否满足堆的结构，如果出现不满足的情况，则对该处的父节点及其子节点做调整，接着检测出现变化的子节点是否是父节点，如果是的话，则检测其作为父节点与自己的子节点是否满足堆结构，如果不满足则继续调整，因此这是一个循环递归的过程，而退出递归的条件则是，是否满足堆结构，故最终我们所构建的大顶堆应该是如下的样式：
通过观察该结构，我们可以发现，堆的顶端，也就是首元素一定是数组中的最大值，故我们将该元素与末尾元素做交换，并将其从堆中移除，也就是说此时我们的8结点元素已经来到了正确的位置了，那么我们需要重新从首元素开始对堆做调整，从而确定第二大的元素，如下所示：
最终我们的实现代码如下：
#include <stdio.h>
void swap(int* temp1, int* temp2) {
int temp;
temp = *temp1;
*temp1 = *temp2;
*temp2 = temp;
return;
}
void ArrDisplay(int* arr, int size) {
for (int i = 0; i < size; i++)
printf("%2d ",arr[i]);
printf("\n");
return;
}
//构建大顶堆
void HeapBuild(int* arr, int NodeIdx, int Last) {
int MaxIdx = NodeIdx;
int NodeLeft = 2 * NodeIdx + 1;
int NodeRight = 2 * NodeIdx + 2;
if (NodeLeft < Last && arr[NodeLeft] > arr[MaxIdx])
MaxIdx = NodeLeft;
if (NodeRight < Last && arr[NodeRight] > arr[MaxIdx])
MaxIdx = NodeRight;
if (NodeIdx != MaxIdx) {
swap(&arr[NodeIdx], &arr[MaxIdx]);
HeapBuild(arr, MaxIdx, Last);
}
return;
}
void HeapSort(int* arr, int size) {
int FNodeNum = size / 2;
//构建堆
for (int i = FNodeNum - 1; i >= 0; i--) {
HeapBuild(arr, i, size);
}
//堆排序
for (int i = size - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
HeapBuild(arr, 0, i);
}
}
int main() {
int Arr[] = { 2,3,4,51,23,26,32,52,1,7 };
int size = sizeof(Arr) / sizeof(int);
HeapSort(Arr, size);
ArrDisplay(Arr, size);
return;
}7、快速排序
首先，我们需要先来了解下快速排序的逻辑，假设我们有如下数组：
此时我们假设首元素为基准值Pivot，我们将小于Pivot的元素都放到他的左侧，而大于他的元素都放在他的右侧，这样的话Pivot这一元素就到了他正确的位置上，那么我们如何实现这一过程呢？其实很简单：
首先，我们先用一个临时变量记录下Pivot，然后我们令两个变量储存数组的下标，用来指向数组的两个端点，我们称他们俩为：哨兵A和哨兵B：
此时哨兵A指向首元素，其作为基准值Pivot，A所指向的元素可以做任意的修改，因此我们要先判断哨兵B，B指向的元素是6，6大于我们的基准值4，由于我们希望Pivot的右侧是大于Pivot的元素，左侧是小于Pivot的值，那么此时我们的B指向的元素不需要移动，所以我们向左移动元素B：
此时B所指向的元素是小于Pivot的，故我们将A的值赋值为B：
?那这个时候B所指向的值是可以任意修改的，故此时我们可以开始移动哨兵A了，由于此时哨兵A所指向的值是2，是小于Pivot的，故移动哨兵A，接着指向1，依旧是小于Pivot的，继续移动哨兵A，直到A移动到下标为3的元素处的时候：
由于5>Pivot，故我们将此时B所指向的值赋值为 A指向的元素：
?这时，我们应该移动B，当B指向下标为6的元素时：
?3<Pivot，故将A赋值为B所指向的元素，再移动B：
?由于B所指向的元素7大于Pivot故不作移动，继续移动B：
?此时B指向的元素3小于Pivot故将A赋值为B所指向的值，再移动A：
此时，哨兵A和B指向了同一个元素，因此我们将其赋值为Pivot即可：
此时我们可以看到4的左侧都是小于4的元素，而4的右侧都是大于4的元素，也就是说此时我们的元素4已经来到了正确的位置上不需要再做任何调换，但无论是4的左侧还是4的右侧仍旧是无须的数组，因此我们需要做的时将两侧的数组做相同的处理，我们把4左侧的数组和4右侧的数组分别取出，并将两个数组的首元素作为Pivot：
通过和刚才相同的处理方法，我们可以将2和7定在正确的位置上，于是再做划分，从而我们可以将整个数组所有的元素都定在正确的位置上，这便是快速排序，最终我们的实现代码如下：
#include <stdio.h>
void swap(int* temp1, int* temp2) {
int temp = *temp1;
*temp1 = *temp2;
*temp2 = temp;
}
void ArrDisplay(int* arr, int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
putchar('\n');
return;
}
void ComSort(int* arr, int left, int right) {
int L = left;
int R = right;
int Pivot = arr[left];
if (left >= right) {
return;
}
while (left < right) {
while (left < right && arr[right] > Pivot)
right--;
arr[left] = arr[right];
while (left < right && arr[left] < Pivot)
left++;
arr[right] = arr[left];
}
arr[left] = Pivot;
ComSort(arr, L, left - 1);//刨除中间值，对左区间进行排序
ComSort(arr, left + 1, R);//刨除右间值，对左区间进行排序
}
// 快速排序入口处
void QuickSort(int* arr, int size) {
int left = 0;
int right = size - 1;
ComSort(arr, left, right);
}
void main() {
int arr[] = { 5,7,8,3,4,12,2,9 };
int size = sizeof(arr) / sizeof(int);
QuickSort(arr, size);
ArrDisplay(arr, size);
return;
}8、归并排序
对于归并排序而言，从字面意思上我们可以把归并排序分为归和并两部分，归的意思时先做归类，并则是合并的意思，对于归并排序来说，其目的是为了将一个包含n个元素的无序数组变成n个有序数组，因为如果一个数组只含有单独元素那么默认就是有序的，而如果我们合并有序数组会容易许多，因此对于归并排序而言最重要的是先做划分，假设有如下的数组：
?首先根据数组下标找到中值，此时左下标为0，右下标为8此时的中值为4，我们将4划分到左区间中，那么我们就得到了下面这样的两个数组：
对于两个新的数组我们依旧做这样的划分：
?这样一直划分下去，直到划分的只剩一个元素位置：
?这样我们就完成了划分的过程，那么接下来就是合并，由于我们合并的是有序数组，那么合并的过程就简单了很多，整个归并排序的过程如下所示：
?那么我们的代码实现过程如下：
#include <stdio.h>
#include <stdlib.h>
int arr[] = { 2,3,4,1,8,6,12,9,10 };
int size = sizeof(arr) / sizeof(int);
void ArrPrint(const int* arr, int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
putchar('\n');
return;
}
void MergeCombine(int* arr, int left, int mid, int right) {
//要和并的区间[left,right]
int* temp = (int*)malloc((right - left + 1) * sizeof(int));
// 标记左半区间和右半区间的首元素
int i = left;
int j = mid + 1;
// 标记临时数组赋值点标记
int k = 0;
// 左半区间和右半区间均还有元素没排好序
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i <= mid && j == right + 1)
temp[k++] = arr[i++];
while (j <= right && i == mid + 1)
temp[k++] = arr[j++];
for (i = left,j = 0; j < k; i++,j++)
arr[i] = temp[j];
free(temp);
return;
}
void MergeDivice(int* arr, int left, int right) {
if (left >= right) return;
int mid = (right + left) / 2;
MergeDivice(arr, left, mid);
MergeDivice(arr, mid + 1, right);
MergeCombine(arr, left, mid, right);
ArrPrint(arr, size);
}
void MergeSort(int* arr, int size) {
int left = 0;
int right = size - 1;
MergeDivice(arr, left, right);
}
int main() {
//ArrPrint(arr, size);
MergeSort(arr, size);
ArrPrint(arr, size);
}