关于基本排序算法的笔记总结
本文仅作为我学习排序算法的笔记参考,原理解释和代码在没有说明的情况下默认指实现从小到大排列,如有错误,欢迎指正。
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. 选择排序
选择排序的效率相较冒泡排序有所提升,原理时从第一个元素开始,把当前的元素记为数列的最小值,然后与后面的元素进行比较,寻找比当前最小值更小的元素,记录下来,一次遍历结束后,就找到后面元素中的最小值,把它与当前元素交换位置,重复这个过程。
代码实现:
// 选择排序,时间复杂度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); // 添加对右半部分的排序
}