学习笔记，可能有些谬误，请批判性阅读。
排序是数据结构的入门问题。过去的巨人们，进行了很大的努力，才使排序的时间复杂度逐步减小。
数组为a，数组长度为n。
必要的边界判断：若n<=1，直接返回。
时间复杂度为)
的思路
选择排序
选择排序是最为直观的排序方法。每次取当前子序列最小的数排在最前面。
第一次，从左往右遍历第1至第n个数，从中选出最小的，和第一个数交换。
第二次，遍历第2至n个数，再从中选出最小的，和第二个数交换。
void select_sort(int* a, int n){
if(n <= 1){
return;
}
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){ //min != i时，需要交换，将i......n中最小的数放到索引i处。
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
插入排序
插入排序像是排列扑克牌，也是一种很直观的排序方法。
手里有张牌已排序，对于新来的第
张牌，与已排好序的
张牌逐张比较大小，若新牌较大，继续向后，直到找到比新牌大的位置
，将新牌插入到位置
，
向后移动一位。
void insert_sort(int* a, int n){
if(n<=1){
return;
}
int temp;
for(int i=1;i<n;i++){
if(a[i]<a[i-1]){//当前元素比前面的子序列的最大数小时，才需要进行插入。
temp = a[i];//存储新牌
for(j=i-1;j>=0;j--){//从后往前遍历前i-1张牌
if(a[j]>temp){//若当前牌仍然大于新牌，当前牌向后挪一张。
a[j+1]=a[j]；
}else{
break;//找到了要插入的位置j
}
}
a[j+1]=temp;//只要进入循环，j--就会运算，因此这里是j+1，
}
}
}
冒泡排序
冒泡排序的思想，相邻两个数比较，若左边数大于右边的，交换。这样相当于较大的数一直往上冒泡，这样遍历一次，最大的数就在数组的最右端了。用同样的思路，比较第1....(n-1)个数，直到只剩下第一个数，排序完成。
void bublle_sort(int* a, int n){
if(n<=1){
return;
}
for(int i=n-1;i>0;i--){//子序列终止位置，i=0时表示子序列只有1个元素，无需再比较。
for(int j=0;j<i;j++){
if(a[j]>a[j+1]){//若左数大于右数，交换
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
中间有个)
希尔排序
最小时间复杂度)
快速排序
快速排序的思想是，以某个值（一般是子序列最左边的值）为标杆，将不大于该标杆的值放在标杆左边，大于的则放在右边。
实现的方法是双指针。左右各一个、或者都从左边出发都可以。这里以左边同时出发来实现。
int partiton(int* a, int start, int end){
int flag = start + 1; //左指针
for(int i = start + 1; i <= end; i++){ // 右指针，初始化时与左指针对齐，用来遍历当前子序列
if(a[i] < a[start]){
// 若右指针元素小于标准a[start]，右指针元素与左指针元素交换，
// 交换后左指针元素比标准值小，不会再发生替换，因此左指针需前进一步
swap(a, i, flag);
flag++;
}
}
flag--;
swap(a, start, flag); // flag需回退一步，指向最后一个标准a[start]小的元素，然后与start位置元素交换。
return flag; // 返回分界点。
}
void helper(int* a, int start, int end){
if(start >= end){ // 子序列为空或者仅剩一个元素，直接返回
return;
}
sep = partition(a, start, end);
helper(a, start, sep - 1);
helper(a, sep + 1, end);
}
void quick_sort(int* a, int n){
if(n<=1){
return;
}
helper(a, 0, n-1);
}
堆排序
堆排序是借助最大堆（或最小堆），首先初始化以数组所有元素组成的最大堆，然后取堆顶元素（最大值）与子序列最右端元素交换。子序列一开始是整个数组，后来是1...(n-1)，直至2个元素构成的子序列。
void adapt_max_heap(int* a, int root, int len){//root为堆顶元素
if(root > floor(len/2)-1){
return;
}
int left = 2 * root + 1;
int right = 2 * right + 1;
int max = root;
if(a[left]>a[max]){
max = left;
}
if(a[right]>a[max]){
max = right;
}
if(max != root){//若check结果，root并不是最大元素，那么需要交换root与max位置对应的元素
int temp = a[root];
a[root] = a[max];
a[max] = temp;
adapt_max_heap(a, max, len); // 调整以max位置元素为根的子堆
}
}
void build_max_head(int* a, int n){
for(int i=floor(n/2.0)-1;i>=0;i--){//从第n/2（取上整）个元素开始，调整堆为最大堆。第n/2个元素只有叶子节点。
adapt_max_heap(a, i, n);
}
}
void heap_sort(int* a, int n){
if(n<=1){
return;
}
build_max_head(a, n); // 先将整个数组初始化为最大堆
for(int i=n;i>1;i--){
int temp = a[0]; // 将堆顶元素置于子序列最后。
a[i-1] = a[0];
a[0] = temp;
adapt_max_heap(a, 0, i-1);
}
}
归并排序
分治思想的典型算法。不断地将序列拆分为两个子序列，各自排序后再进行合并。
思想最直观，实现起来却最复杂，尤其是C++版本的。
参考[1]实现。
void merge(int* a, int* b, int l, int m, int r){
// a是原始数组，a[l...m]，a[m+1...r]分别是左右两个子序列
// b是个辅助数组，用来暂存排归并后的序列。
int i = l;
int j = m + 1;
int k = l;
while(k <= r){
if(i > m){ // 左子序列遍历完成
b[k++] = a[j++];
}else if(j > r){ // 右子序列遍历完成
b[k++] = a[i++];
}else{
if(a[i] <= a[j]){ // 取较小值放入b
b[k++] = a[i++]；
}else{
b[k++] = a[j++]；
}
}
}
for(k = l; k <= r; k++){ // 将排好序合并起来的结果复制到数组a的对应位置。
a[k] = b[k];
}
}
void merge_sort_helper(int* a, int* b, int l, int r){
if(l >= r){
return;
}
mid = (l + r) / 2;
merge_sort_helper(a, b, l, mid);
merge_sort_helper(a, b, mid + 1, r);
merge(a, b, l, mid, r);
}
void merge_sort(int* a, int n){
if(n<=1){
return
}
int* b = new int[n];
merge_sort_helper(a, b, 0, n - 1);
delete b; // 最后要删除临时数组。
}
其中最后一行代码delete[] b亦可，参考[2]
总结
TO BE CONTINUED
参考
[1] https://www.jianshu.com/p/e6dbb83a2e6d
[2] https://www.runoob.com/note/15971
网友评论