基础的排序算法下（交换排序和归并排序）

1：交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置 交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1：冒泡排序（每个计算机学生必掌握的第一个算法）

直接看代码吧，太简单不讲了

void BubbleSort(int* a, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j+1]) { Swap(&a[j], &a[j+1]); } } } } 2:快速排序（递归版本）

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均小于基准值，右子序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为止。（本质上是找基准数）

我们先把主题void函数写出来

void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int keyi = PartSort(a, left, right);//找基准值函数 QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } 1：快速排序hoare版本 int PartSort1(int* a, int left, int right) { int keyi = left; ++left; while (left <= right) { while (left <= right && a[right] > a[keyi]) { --right; } while (left <= right && a[left] < a[keyi]) { ++left; } if (left <= right) { Swap(&a[right--], &a[left++]); } } Swap(&a[keyi], &a[left-1]); return left-1; }

基本思路：

1：创建左右指针，确定基准值

2：从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

2：快速排序挖空法 int PartSort2(int* a, int left, int right) { int hole = left; int key = a[hole]; 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; }

基本思路：

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

3：快速排序前后指针法 int PartSort3(int* a, int left, int right) { int keyi = left; int prev = left, cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[prev], &a[keyi]); return prev; }

基本思路：

创建前后指针，从左往右找比基准值小的进行交换，使小的都排在基准值左边。

3：快速排序（非递归版本借助stack实现） void QuickSortNonR(int* a, int left, int right) { Stack st; StackInit(&st); StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); int keyi = begin; int prev = begin, cur = prev + 1; while (cur <= end) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; if (keyi + 1 < end) { StackPush(&st, end); StackPush(&st, keyi + 1); } if (begin < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, begin); } } StackDestroy(&st); } 2：归并排序 1：归并排序递归实现 void _MergeSort(int* arr, int left, int right, int* tmp)//辅助函数 { if (left >= right) { return; } int mid = (left + right) / 2; _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) { 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++]; } for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } void MergeSort(int* a, int n)//声明 { int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(a, 0, n - 1, tmp); free(tmp); }

基本思路：归并排序（MERGE - SORT）是建⽴在归并操作上的⼀种有效的排序算法, 该算法是采⽤分治法（Divideand Conquer）的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。 

2：归并排序非递归实现 void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; if (begin2 >= n) { break; } if (end2 >= n) { end2 = n-1; } int index = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a+i, tmp+i, sizeof(int) * (end2 - i + 1)); } gap *= 2; } free(tmp); tmp = NULL; } 3:计数排序（非比较排序） void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 1; i < n; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } int range = max - min + 1; int* cout = (int*)malloc(sizeof(int) * range); if (cout == NULL) { perror("malloc fail"); } memset(cout, 0, sizeof(int) * range); for (int i = 0; i < n; i++) { cout[a[i] - min]++; } int index = 0; for (int i = 0; i < range; i++) { while (cout[i]--) { a[index++] = i + min; } } } 计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤： 1：统计相同元素出现次数 2：根据统计的结果将序列回收到原来的序列中