动图演示 | C++实现六大排序算法
1、插入排序
1.1 算法描述
每次选择一个元素，并且将这个元素和整个数组中的所有元素进行比较，然后插入到合适的位置，图片演示如上，时间复杂度 O(n²)。
1.2 动图演示
1.3 代码实现
void insertion_sort(int arr[], int length){
int i, j;
for(i = 1; i < length; i++){
int tmp = arr[i];
for(j = i; j > 0 && arr[j - 1] > tmp; j--){
arr[j] = arr[j - 1];
}
arr[j] = tmp;
}
}
2、冒泡排序
2.1 算法思想
每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来，时间复杂度O(n²)。
2.2 动图演示
2.3 代码实现
void bubble_Sort(int arr[], int length){
int i, j;
bool swap;
for(i = 0; i < length - 1; i++){
swap = false;
for(j = 0; j < length - i - 1; j++){
if(arr[j] > arr[j + 1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swap = true;
}
}
if(!swap) break;
}
}
3、选择排序
3.1 算法思想
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 时间复杂度O(n²)。
3.2 动图演示
3.3 代码实现
void selection_sort(int arr[], int length){
int i, j;
int minIndex;
for(i = 0; i < length - 1; i++){
minIndex = i;
for(j = i + 1; j < length; j++){
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
if(minIndex != i){
int tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
4、归并排序
4.1 算法思想
归并排序相比较之前的排序算法而言加入了分治法的思想，其算法思路如下：
1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）。
2.把整个数组分为尽可能相等的两个部分（分）。
3.对于两个被分开的两个部分进行整个归并排序（治）。
4.把两个被分开且排好序的数组拼接在一起。
时间复杂度O(nlogn)。
4.2 动图演示
4.3 代码实现
void merge(int arr[], int l, int m, int r){
int i, j;
int llen = m - l + 1;
int rlen = r - m;
int L[llen], R[rlen];
for(i = 0; i < llen; i++) L[i] = arr[l + i];
for(j = 0; j < rlen; j++) R[j] = arr[m + 1 + j];
i = 0; j = 0;
int k = l;
while(i < llen && j < rlen){
if(L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
while(i < llen) arr[k++] = L[i++];
while(j < rlen) arr[k++] = R[j++];
}
void merge_sort(int arr[], int l, int r){
if(l >= r) return;
int m = l + (r - l) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
5、堆排序
5.1 算法思想
首先需要引入最大堆的定义：
1.最大堆中的最大元素值出现在根结点（堆顶）。
2.堆中每个父节点的元素值都大于等于其孩子结点。
堆排序的方法如下，把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。
时间复杂度O(nlogn)。
5.2 动图演示
5.3 代码实现
可以自己实现最大堆或者直接使用C++的优先队列。
最大堆
void heap_build(int arr[], int n, int i){
// 大顶堆
int maxIdx = i;
// 计算当前节点的左右孩子节点
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[maxIdx])
maxIdx = l;
if (r < n && arr[r] > arr[maxIdx])
maxIdx = r;
if (maxIdx != i)
{
int tmp = arr[maxIdx];
arr[maxIdx] = arr[i];
arr[i] = tmp;
// 递归调整子堆
heap_build(arr, n, maxIdx);
}
}
void heap_sort(int arr[], int n){
// 建立堆
for(int i = n / 2 - 1; i >= 0; i--)
heap_build(arr, n, i);
// 一个个从堆顶取出元素
for(int i = n - 1; i>=0; i--)
{
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
heap_build(arr, i, 0);
}
}
优先队列
C++中priority_queue默认实现的是大顶堆
int main()
{
// 大顶堆
//priority_queue<int, vector<int>, less<int> > a 或者
//priority_queue<int> a;
// 小顶堆
priority_queue<int, vector<int>, greater<int> > que;
int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
for(int num : arr) que.push(num);
while(!que.empty()){
cout<<que.top()<<' ';
que.pop();
}
//out：2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
}
6、快速排序
6.1 算法思想
快排也是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，根据实现算法的不同，元素的选择一般有如下几种：
1.永远选择第一个元素
2.永远选择最后一个元素
3.随机选择元素
4.取中间值
整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
时间复杂度O(nlogn)。
6.2 动图演示
6.3 代码实现
下面代码以最右端为基准值
void quick_sort(int arr[], int l, int r){
if(l >= r) return;
int i = l, j = r;
int target = arr[r];
while(i < j)
{
while(i < r && arr[i] < target) // 从左向右找第一个大于等于x的数
i++;
while(i < j && arr[j] >= target) // 从右向左找第一个小于x的数
j--;
if(i < j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
arr[r] = arr[i];
arr[i] = target;
quick_sort(arr, l, i - 1);
quick_sort(arr, i + 1, r);
}