数据结构十五、排序

一、插入排序

插入排序（insertion sort）类似于扑克牌的插牌过程，将待排序元素插入到已排序的序列中。

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];void insert_sort()
{for (int i = 2;i <= n;i++) //第一个位置默认有序{int key = a[i];int j = i - 1;while (a[j] > key && j >= 1){a[j + 1] = a[j];j--;}a[j + 1] = key;}
}

二、选择排序

选择排序（selection sort），每次找出未排序序列中最小的元素，然后放进有序序列的后面。

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];void selection_sort()
{for (int i = 1;i < n;i++){int pos = i;for (int j = i + 1;j <= n;j++){if (a[j] < a[pos])pos = j;}swap(a[i], a[pos]);}
}

三、冒泡排序

冒泡排序（bubble sort），执行n-1趟操作，每次检查相邻两个元素，如果逆序就交换。

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];void bubble_sort()
{for (int i = n;i > 1;i--){bool flag = false;for (int j = 1;j < i;j++){if (a[j] > a[j + 1])swap(a[j], a[j + 1]);flag = true;}if (flag == false)return;}
}

四、堆排序

堆排序（heap sort）是指利用堆这种数据结构所设计的一种排序算法。堆排序的过程分两步：1、建堆。从倒数第一个非叶子节点开始，每个节点进行向下调整。2、排序。删除堆顶元素的逻辑。因此，堆排序仅需用到向下调整算法。

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];void down(int parent, int len)
{int child = parent * 2;while (child <= len){if (child + 1 <= n && a[child] < a[child + 1])child++;if (a[parent] > a[child])return;swap(a[parent], a[child]);parent = child;child = parent * 2;}
}void heap_sort()
{for (int i = n / 2;i >= 1;i--){down(i, n);}for (int i = n;i > 1;i--){swap(a[i], a[1]);down(1, i - 1);}
}

五、快速排序

快速排序（quick sort），核心算法原理可以分为两步：1、从待排序区间中选择一个基准元素，按照基准元素的大小将区间分成左右两部分。2、然后递归处理左区间和右区间，直到区间长度为1。

优化一、随机选择基准元素

随机函数：srand（time（0））——>种下一个随机种子

rand（）——>获得一个随机数

rand（）%（right - left + 1）+ left——>在[left, right]区间内随机选择一个数

优化二、三路划分

将所有元素分成三个区间：左边全部小于基准元素，中间全部等于基准元素，右边全部大于基准元素。那么接下来只需要递归处理左右区间，中间区间就可以无需考虑。

代码实现

#include <iostream>
using namespace std;const int N = 1e5 + 10;
int n;
int a[N];int get_random(int left, int right)
{return a[rand() % (right - left + 1) + left];
}void quick_sort(int left, int right)
{if (left >= right)return;int p = get_random(left, right);int l = left - 1;int i = left;int r = right + 1;while (i < right){if (a[i] == p)i++;else if (a[i] > p){swap(a[i], a[r]);r--;}else{swap(a[i], a[l]);l++;i++;}}quick_sort(left, l);quick_sort(r, right);
}int main()
{srand(time(0));return 0;
}

六、归并排序

归并排序（merge sort）用的是分治思想，它的主要过程分两步：1、将整个区间一分为二，先把左边和右边排序；2、然后将左右两个区间合并在一起。其中，如何让左右两边有序，就继续使用归并排序，因此，归并排序是用递归实现的。

#include <iostream>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];
int tmp[N];void merge_sort(int left, int right)
{if (left >= right)return;int mid = (left + right) >> 1;merge_sort(left, mid);merge_sort(mid + 1, right);int cur1 = left;int cur2 = mid + 1;int i = left;while (cur1 <= mid && cur2 <= right){if (a[cur1] <= a[cur2]){tmp[i] = a[cur1];cur1++;i++;}else{tmp[i] = a[cur2];cur2++;i++;}}while (cur1 <= mid){tmp[i] = a[cur1];i++;cur1++;}while (cur2 <= right){tmp[i] = a[cur2];cur2++;i++;}for (int j = left;j <= right;j++){a[j] = tmp[j];}
}