本文仅作为我学习排序算法的笔记参考，原理解释和代码在没有说明的情况下默认指实现从小到大排列，如有错误，欢迎指正。关于基本排序算法的笔记总结
本文仅作为我学习排序算法的笔记参考，原理解释和代码在没有说明的情况下默认指实现从小到大排列，如有错误，欢迎指正。
1. 冒泡排序
冒泡排序是最为简单的排序算法，原理是遍历数列中的元素，与相邻的元素进行比较，如果大于（或小于）后面的元素则交换位置，循环结过程中，较大的（或较小的）元素就会“冒泡”到数列的末尾，直到循环结束，数列有序排列。
// 冒泡排序，时间复杂度O(n^2)
void PopSort(int a[], int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - 1; j++){if (a[j] > a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}
它的显著特征是两层循环嵌套，这也使得它在样本较大的情况下效率较低。
2. 选择排序
选择排序的效率相较冒泡排序有所提升，原理时从第一个元素开始，把当前的元素记为数列的最小值，然后与后面的元素进行比较，寻找比当前最小值更小的元素，记录下来，一次遍历结束后，就找到后面元素中的最小值，把它与当前元素交换位置，重复这个过程。
graph TDA[选择第一位为最小值] --> B[遍历]B --> C[寻找最小值]C --> D[与第一位交换]D --> E[选择第二位为最小值]E --> F[遍历]F --> G[……]
代码实现：
// 选择排序，时间复杂度O(n^2)
void SelectSort(int a[], int n)
{for (int i = 0; i < n; i++){int min = i;for (int j = i + 1; j < n; j++){if (a[j] < a[min]){min = j;}}if (min != i){int temp = a[i];a[i] = a[min];a[min] = temp;}}
}同样是两层嵌套循环，选择排序因为平均交换次数较少（n次），所以效率比冒泡排序要稍高。
3. 插入排序
插入排序有点类似我们整理扑克牌的过程。从第二个元素开始，我们暂存这个元素，与前面的元素进行比较，如果前面的第j位元素比当前的元素大，我们就把j复制并覆盖掉j+1的位置（相当于把前面的元素向后移动），继续向下比较并重复这个子过程，直到找到比当前元素小的元素，然后插入到该元素后面，如果遍历到开头仍没有找到，就维持不动。第三个元素以此类推，直到最后一个元素。
// 插入排序，时间复杂度O(n^2)
void InsertSort(int a[], int n)
{for (int i = 1; i < n; i++){int temp = a[i]; // 提取需要插入的元素int j = i - 1; // 从前面排序过的元素开始while (j >= 0 && a[j] > temp){a[j + 1] = a[j]; // 如果大于，就将排序过的元素向右移动j--; // 继续向左遍历比较}// 跳出循环即找到合适的位置，插入a[j + 1] = temp;}
}插入排序的时间复杂度与冒泡排序和选择排序相同，但它的平均交换次数更少，所以效率更高。
4. 归并排序
归并排序是一种分治法，较为复杂。将给定数组以大致中心为基准分为两个子数组，以递推的形式不断进行下去，直到两个子数列只剩下1个元素，然后开始合并，合并时将两个子数列按顺序合并，直到合并完成。
// 归并排序，时间复杂度O(nlogn)
void MergeSort(int a[], int left, int right)
{if (left >= right)return;int mid = (left + right) / 2;MergeSort(a, left, mid);MergeSort(a, mid + 1, right);int temp[right - left + 1];int i = left, j = mid + 1, k = 0;// 两个子数列按顺序排到temp中while (i <= mid && j <= right){if (a[i] < a[j])temp[k++] = a[i++];elsetemp[k++] = a[j++];}while (i <= mid)temp[k++] = a[i++];while (j <= right)temp[k++] = a[j++];// 将temp复制到a中for (int p = 0; p < k; p++){a[left + p] = temp[p];}
}
归并排序的时间复杂度是O(nlogn)，以空间换时间，效率较高。中间连个子数列按序合并的过程在稿纸自行模拟即可理解，不多阐述。
5. 两种快速排序
快速排序也采取了分治法，不过它是先整理再分治。以（子）数列中的一个元素为基准，将比它小的元素放在它前面，比它大的元素放在它后面，然后递归地以同样的方式对前后两个子数列进行排序，直到两个子数列都只剩一个元素。由基准的选择方式不同，分为快速排序和随机快速排序
快速排序
可以选择第一个、最后一个、中间的元素等作为基准，总之基准的位置是固定的
// 快速排序，时间复杂度O(nlogn)
void QuickSort(int a[], int low, int high)
{if (low >= high)return;int base = a[low];int i = low, j = high;while (i < j){// 从右向左找第一个小于base的数while (i < j && a[j] >= base)j--;if (i < j)a[i++] = a[j];// 从左向右找第一个大于base的数while (i < j && a[i] <= base)i++;if (i < j)a[j--] = a[i];}a[i] = base;QuickSort(a, low, i - 1);QuickSort(a, i + 1, high);
}
随机快速排序
基准是随机的，这样能避免最坏情况的发生，但是也增加了不稳定性。其余内容与快速排序相同。
// 随机快速排序，时间复杂度O(nlogn)
void RandomQuickSort(int a[], int low, int high)
{if (low >= high) // 添加递归终止条件return;int base = a[rand() % (high - low + 1) + low];int i = low, j = high;while (i < j){// 从右向左找第一个小于base的数while (i < j && a[j] >= base)j--;if (i < j)a[i++] = a[j];// 从左向右找第一个大于base的数while (i < j && a[i] <= base)i++;if (i < j)a[j--] = a[i];}a[i] = base;RandomQuickSort(a, low, i - 1);RandomQuickSort(a, i + 1, high); // 添加对右半部分的排序
}
调试代码
附上调试代码：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>int a[100];
void PopSort(int a[], int n);
void SelectSort(int a[], int n);
void InsertSort(int a[], int n);
void MergeSort(int a[], int left, int right);
void QuickSort(int a[], int left, int right);
void RandomQuickSort(int a[], int left, int right);int main(int argc, char const *argv[])
{srand(time(0));clock_t start, end;for (int i = 0; i < 300; i++){a[i] = rand() % 100;}int n = sizeof(a) / sizeof(a[0]);int temp[n]; // 用于重置数组// 复制原始数组for (int i = 0; i < n; i++){temp[i] = a[i];}start = clock();for (int i = 0; i < 100000; i++){// 重置数组for (int j = 0; j < n; j++){a[j] = temp[j];}// PopSort(a, n);// InsertSort(a, n);QuickSort(a, 0, n - 1);}end = clock();// 检验排序正确性// for (int i = 0; i < n; i++)// {// printf("%d ", a[i]);// }printf("\ntime: %fms\n", (double)(end - start));return 0;
}// 冒泡排序，时间复杂度O(n^2)
void PopSort(int a[], int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - 1; j++){if (a[j] > a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}
}// 选择排序，时间复杂度O(n^2)
void SelectSort(int a[], int n)
{for (int i = 0; i < n; i++){int min = i;for (int j = i + 1; j < n; j++){if (a[j] < a[min]){min = j;}}if (min != i){int temp = a[i];a[i] = a[min];a[min] = temp;}}
}// 插入排序，时间复杂度O(n^2)
void InsertSort(int a[], int n)
{for (int i = 1; i < n; i++){int temp = a[i]; // 提取需要插入的元素int j = i - 1; // 从前面排序过的元素开始while (j >= 0 && a[j] > temp){a[j + 1] = a[j]; // 如果大于，就将排序过的元素向右移动j--; // 继续向左遍历比较}// 跳出循环，找到合适的位置，插入a[j + 1] = temp;}
}// 归并排序，时间复杂度O(nlogn)
void MergeSort(int a[], int left, int right)
{if (left >= right)return;int mid = (left + right) / 2;MergeSort(a, left, mid);MergeSort(a, mid + 1, right);int temp[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right){if (a[i] < a[j])temp[k++] = a[i++];elsetemp[k++] = a[j++];}while (i <= mid)temp[k++] = a[i++];while (j <= right)temp[k++] = a[j++];for (int p = 0; p < k; p++){a[left + p] = temp[p];}
}// 快速排序，时间复杂度O(nlogn)
void QuickSort(int a[], int low, int high)
{if (low >= high)return;int base = a[low];int i = low, j = high;while (i < j){// 从右向左找第一个小于base的数while (i < j && a[j] >= base)j--;if (i < j)a[i++] = a[j];// 从左向右找第一个大于base的数while (i < j && a[i] <= base)i++;if (i < j)a[j--] = a[i];}a[i] = base;QuickSort(a, low, i - 1);QuickSort(a, i + 1, high);
}// 随机快速排序，时间复杂度O(nlogn)
void RandomQuickSort(int a[], int low, int high)
{if (low >= high) // 添加递归终止条件return;int base = a[rand() % (high - low + 1) + low];int i = low, j = high;while (i < j){// 从右向左找第一个小于base的数while (i < j && a[j] >= base)j--;if (i < j)a[i++] = a[j];// 从左向右找第一个大于base的数while (i < j && a[i] <= base)i++;if (i < j)a[j--] = a[i];}a[i] = base;RandomQuickSort(a, low, i - 1);RandomQuickSort(a, i + 1, high); // 添加对右半部分的排序
}