八大排序的那些事儿

1.排序-冒泡算法

讲算法太空洞，直接上实例：

上实例中，当后面的都已经排序好的时候其实是不需要交换的，所以就会终止循环。

利用递归的方式写冒泡排序：

2. 归并排序

归并排序是把待排序序列分为若干个子序列，每个子序 列是有序的。然后再把有序子序列合并为整体有序序列。先把待排序列分为两部分，然后各部分再分为两部分，一直分下去，直到不能再分为 止，然后在两两合并两个有序数组，直到合并完为止。

3.插入排序

插入排序的原理是默认前面的元素都是已经排序好的，然后从后面逐个读取插入到前面 排序好的合适的位置，就相当于打扑克的时候每获取一张牌的时候就插入到合适的位置 一样。插入排序可以分为两种，一种是直接插入还一种是二分法插入，直接插入的原理 比较简单，就是往前逐个查找直到找到合适的位置然后插入。

二分法插入排序：

4.基数排序

基数排序是非比较排序算法,算法的时间复杂度是O(n)。 基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始, 依次进行一次稳定排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

#include <iostream>
using namespace std;
/*********************************************************
Function:rxsort
Description:基数排序
Input:
数组A[l,h]；
数组中最大元素的位数d，例如最大数为999，则d为3；
进制数k，如果是10进制数，k为10；
Output:排序好的数组；
Others：对数字1234来说，预定第0位为4，第1位为3，依次类推；
*********************************************************/
bool rxsort(int A[],int l,int h,int d,int k){
if(NULL==A||l>h)
return false;
int size = h-l+1;

int* counts = new int[k];//用于计数排序的辅助数据，详见计数排序
int* temp = new int[size];//用于存储重新排序的数组
int index;
int pval=1;
//依次处理不同的位
for(int i=0;i<d;i++){
//counts数组清零
for(int j=0;j<k;j++)
counts[j] = 0;

for(int j=l;j<=h;j++){
/*
1.data[j]/pval：去掉数字data[j]的后i个数，例如：
当data[j]=1234,i=2时，此时pval=100,data[j]/pval=12;
2.(data[j]/pval)%k：取数字data[j]/pval的最后一位数
3.(int)(data[j]/pval)%k:取数字data[j]的第i位数
*/
index = (int)(A[j]/pval)%k;
/*
统计数组A中每个数字的第i位数中各个数字的频数,用于计数排序；
*/
counts[index]++;
}
//计算累加频数，用户计数排序
for(int j=1;j<k;j++)
counts[j] = counts[j] + counts[j-1];
//使用倒数第i+1位数对A进行排序
for(int j=h;j>=l;j--){
index = (int)(A[j]/pval)%k;
temp[counts[index]-1] = A[j];
counts[index]--;
}
//将按第i为数排序后的结果保存回数组A中
for(int j=0;j<size;j++)
A[j+l] = temp[j];
//更新pval
pval = pval*k;
}
delete[] counts;
delete[] temp;
}

int main(){
int A[] = {712,303,4,18,89,999,70,26};
rxsort(A,0,7,3,10);
for(int i=0;i<8;i++)
cout<<A[i]<<" ";
}

5.快速排序

快速排序原理是首先要找到一个中枢，把小于中枢的值放到他前面，大于中枢的值放到 他的右边，然后再以此方法对这两部分数据分别进行快速排序。

6.选择排序

选择排序和冒泡排序有一点点像，选择排序是默认前面都是已经排序好的，然后从后面 选择最小的放在前面排序好的的后面，首先第一轮循环的时候默认的排序好的为空，然 后从后面选择最小的放到数组的第一个位置，第二轮循环的时候默认第一个元素是已经 排序好的，然后从剩下的找出最小的放到数组的第二个位置，第三轮循环的时候默认前 两个都是已经排序好的，然后再从剩下的选择一个最小的放到数组的第三个位置，以此类推。

7.堆排序

堆排序，也可以理解为二叉树排序，这里的堆分为两种，一种是大 顶堆，一种是小顶堆，我们所有的排序方法都以升序为主，其实倒序原理也都差不多

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void adjust(int arr[], int len, int index)
{
int left = 2*index + 1;
int right = 2*index + 2;
int maxIdx = index;
if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
if(maxIdx != index)                 // 如果maxIdx的值有更新
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
}

}
void heapSort(int arr[], int size)
{
for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
{
adjust(arr, size, i);
}
for(int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
}
}

int main()
{
int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
heapSort(array, 8);
for(auto it: array)
{
cout<<it<<endl;
}
return 0;
}

8.shell(希尔)排序

shell排序在不相邻的元素之间比较和交换。利用了插入排序的最佳时间代价特性，它试图将待排序序列变成基本有序的，然后再用插入排序来完成排序工作。在执行每一次循环时，Shell排序把序列分为互不相连的子序列，并使各个子序列中的元素在整个数组中的间距相同，每个子序列用插入排序进行排序。

#include<iostream>

using namespace std;
const int INCRGAP = 2;
void shellSort(int a[],int len)
{
int insertNum = 0;
unsigned gap = len/INCRGAP; // 步长初始化
while(gap) // while gap>=1
{
for (unsigned i = gap; i < len; ++i) // 分组，在每个子序列中进行插入排序
{
insertNum = a[i];//将当前的元素值先存起来方便后面插入
unsigned j = i;
while (j >= gap && insertNum < a[j-gap])//寻找插入位置
{
a[j] = a[j - gap];
j -= gap;
}
a[j] = insertNum;
}
gap = gap/INCRGAP;
}
}
int main()
{
int array[11] = {2, 1, 4, 3, 11, 6, 5, 7, 8, 10, 15};
shellSort(array, 11);
for(auto it: array)
{
cout<<it<<endl;
}
return 0;
}