1，插入排序

时间复杂度O(N)

思路：当插入第i个元素时，前面i-1个元素已经排好，将第i个元素与前面的元素比较，找到插入的位置，原来位置的元素向后挪。

动图展示：

从上图可以看出，先把第一个数据看成有序，第二个数据和他比较，如果小的话，将第一个数据往后挪动，第二个数据插入到第一个位置。依次类推，再将前两个数据看成是有序的，第三个数据与前两个数据比较插入，前三个数据看成是有序的，第四个数据与前面数据比较插入......直到最后一个数据也比较完成，数据就有序了

代码实现：

//插入排序
void InsertSort(int* a, int n)
{//i<n-1,防止越界for (int i = 0; i < n - 1; i++){//单趟，一个数据和前面的数据比较插入//[0,end]区间有序int end = i;//tmp为要与前面比较的元素，先保存下来int tmp = a[end + 1];while (end >= 0){//如果大于，数据往后挪动if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}//插入数据a[end + 1] = tmp;}
}

2，希尔排序

时间复杂度O(N^1.3)

希尔排序分思路：

1，预排序，经过多组预排序，让整个数组很接近有序

2，插入排序,最有一趟进行插入排序

预排序：先将数据分成gap组，再对每组进行插入排序。假设gap=3

一组预排序：

预排序的实现，就是在原数组上进行插入排序，这个插入排序与上面的不同，上面的插入排序可以认为跨度是1，而这里的插入排序跨度是gap。

预排序的代码：

for (int i = 0; i < gap; i++)
{//排一组，i=0时，排蓝色一组for (int j = i; j < n - gap; j += gap){//[0，end]有序，让end+gap位置与前面进行比较插入int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
}

 上面预排序的代码，实际上是一组一组排，i=0时，将蓝色一组排好，i=1时，将红色这一组排好，i=2时，将黄色这一组排好，起始代码可以进行改进，如下：

for (int i = 0; i < n-gap; i++)
{//[0，end]有序，排end+gap位置int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}

而这种是多组并着排，相当于蓝色组排一次，红色组排一次，黄色组再排一次。然后循环继续，又是 蓝色组排一次，红色组排一次，黄色组再排一次。

但是这两种方式对于效率方面没有提高。

最后，整个代码实现大致思路:控制gap，gap>1时进行预排序，gap=1时，进行最后那一组插入排序。

//希尔排序
void ShellSort(int* a, int n)
{int gap = n;//gap组while (gap > 1){//gap>1时，先进行预排序//gap=1时，进行插入排序gap = gap / 3 + 1;//排多组，一组一组排for (int i = 0; i < gap; i++){//排一组，i=0时，排蓝色一组for (int j = i; j < n - gap; j += gap){//[0，end]有序，让end+gap位置与前面进行比较插入int end = j;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}}

3，选择排序

时间复杂度O(N^2)

思路：一组数据中，遍历一遍，选出最小的数和最大的数，分别放到第一个位置和最后一个位置，然后除这两个元素外，再将剩下的元素进行遍历选数，依次循环。

//选择排序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){//选数int mini = begin, maxi = begin;for (int i = begin+1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}swap(a[begin], a[mini]);if (maxi == begin)//最大数的位置是开始位置时，经过上一步代码，最大值会被换到mini位置{maxi = mini;}swap(a[end], a[maxi]);begin++;end--;}
}

4，快速排序

时间复杂度：O(N*logN)

1,hoare版本

动图展示：

思路：选取左边第一个位置做key,右边先走，右边找小，找到比key位置小的数停下，左边找大，找到比key位置大的数停下，然后交换。最后L与R会相遇，相遇位置一定比key小，再与key交换。这样就完成了一趟。最后的结果是，key左边的数都比key小，key右边的数都比key大， 也就是说key的位置确定了，不用动了。这时，整个数组被分成了三部分，[left,key-1] key [key+1,right],key这个位置已经确定了，所以我们接下来只需对[left,key-1]  [key+1,right]两部分排序就好了，同样，采用相同的方法。这就需要用到递归来解决了。

代码实现：

//快速排序  hoare
void QuickSort(int* a, int left, int right)//right指向最后一个元素
{if (left >= right)return;int keyi = left;int begin = left, end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi]){--end;}//左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}swap(a[begin], a[end]);//调用c++库里的swap}//相遇swap(a[begin], a[keyi]);keyi = begin;//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi - 1);//递归作区间QuickSort(a, keyi + 1, right);//递归右区间
}

 2，前后指针

动图展示：

思路：key为第一个位置下标，用cur遍历整个数组，开始时，prev指向第一个位置，cur指向prev+1位置，cur找小，找到比key位置小的 ，与prev下一个位置交换，cur找到大的++，直到遍历完整个数据。最后，prev位置和key位置交换，同理继续递归左右子区间。

代码实现

//快速排序  前后指针
void QuickSort1(int* a, int left, int right)//right指向最后一个元素
{if (left >= right)return;int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//prev和cur重合时，不交换{swap(a[cur], a[prev]);}++cur;}swap(a[prev], a[keyi]);keyi = prev;//[left,keyi-1] keyi [keyi+1,right]QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

 3，优化

对于快排，在排有序数组时，效率会大大降低，当数据量足够大的时候，会出现栈溢出的情况。

上面这种情况，n个数据，key一直在第一个位置，左区间不存在，一直递归右区间 。递归层数太深，会出现栈溢出的情况。

解决方法是，让key位置不是最小的，采用三数取中的方法。取第一个位置，中间位置和最后一个位置数据三个数据中的中间值。

还有一种情况，在递归调用时，为了减少递归调用次数，可以在数据量较小时，采用插入排序。

优化后的代码：

int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] > a[right]){return left;}else{return right;}}else//a[left] >= a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}
//快速排序  hoare
void QuickSort(int* a, int left, int right)//right指向最后一个元素
{if (left >= right)return;//减少递归次数if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}else{//三数取中int midi = GetMidi(a, left, right);swap(a[midi], a[left]);int keyi = left;int begin = left, end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi]){--end;}//左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}swap(a[begin], a[end]);}//相遇swap(a[begin], a[keyi]);keyi = begin;//[left,keyi-1] keyi [keyi+1,right]QuickSort(a, left, keyi - 1);//递归作区间QuickSort(a, keyi + 1, right);//递归右区间}
}

4，非递归

这里用数据结构的栈来模拟实现

快排的本质是，选出key,对左右区间递归排序。对左区间进行排序，选出key,递归左右区间。左区间排好后，再对右区间进行排序，选出key。排序的逻辑还是不变（hoare或者是前后指针）。

思路：我们可以使用栈来存储要排序的区间，排序时取出栈顶的数据，也就是要排序的区间，

然后选出key，再对左右区间进行入栈（前提是区间合法），结束条件是栈为空，没有区间需要排序了。

 代码实现（这里的排序逻辑是前后指针方式）

//快排非递归
void QuickSortNor(int* a, int left, int right)
{stack<int> st;//先右后左st.push(right);st.push(left);while (!st.empty()){int begin = st.top();st.pop();int end = st.top();st.pop();//排序，选出keyiint keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){swap(a[cur], a[prev]);}++cur;}swap(a[prev], a[keyi]);keyi = prev;//[begin,keyi-1] keyi [keyi+1,end]//先入右区间if (keyi+1<end){st.push(end);st.push(keyi + 1);}if (begin < keyi - 1){st.push(keyi - 1);st.push(begin);}}
}

 5，归并排序

时间复杂度O(N*logN)

空间复杂度(N)

1，递归

动图展示：

思路：需要开辟一个数组，如果将数据分成两部分，这两部分都有序， 这两部分数据从开始位置比较，小的拿下来放入新数组中，直到把这两部分数据都拿下来。最后再把新数组拷贝回原数组中。但是分成的这两部分不一定是有序的，所以就要用到递归解决，递归使这两部分变成有序的，

然后再进行比较，拷贝（重复上面的逻辑）。

这里递归结束条件：分成的两部分只有一个数据。这时就可以开始归并了。

对于左右两部分的划分，用的是二分。begin为开始位置，mid为中间位置，end为最后位置，

左右两部分应划分为【begin,mid】，【mid+1,end】。

不能划分为【begin,mid-1】，【mid，end】。 

代码实现：

void _MerageSort(int* a, int* tmp,int begin, int end)
{if (begin == end)return;int mid = (begin + end) / 2;//左右区间有序就进行归并//[begin,mid]  [mid+1,end]//不能将区间分成[begin,md-1] [mid,end]会出现栈溢出_MerageSort(a, tmp,begin, mid);//让左边有序_MerageSort(a, tmp,mid+1, end);//让右边有序//两边有序后，开始归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}if (a[begin2] <= a[begin1]){tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MerageSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MerageSort(a, tmp,0, n - 1);
}

 2，非递归

 

思路：一次循环，对数组进行一一归并， 第二次循环，进行两两归并。可以定义一个gap变量，

表示每组归并的数据个数。gap=1时，就进行一一归并。

 

对于这两个区间，[begin1,end1] [begin2,end2],就拿第一次循环举例，gap=1时，这两个区间为[0,0],[1,1]，然后这两个区间开始归并。for循环一次 后，只归并了前两个数据，就是前面图中的10，6进行归并了，要想继续归并后面的数据，下一个开始归并的起始位置为2*gap,也就是图中的7,for循环后，7和1就归并好了......  这样就完成了一次一一归并。

 

控制gap就可以完成了，实现两两归并，四四归并。 

但是，这个代码还有问题，对于所划分的区间[begin1,end1],[begin2,end2]可能存在越界的风险，end1,begin2,end2可能会越界。因为数据个数不一定是2的次方倍。

三种情况：

1，end1越界，begin2越界，end2越界

2，begin2越界，end2越界

3，end2越界

前两种情况，不用归并了，第二个区间不存在。

第三种情况，需要归并，只需对end2进行修改，让它指向最后一个元素即可。

完整代码展示：

//归并排序 非递归
void MerageSortNor(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;//每组数据个数//gap=1  一一归并while (gap < n){for (int i = 0; i < n; i += 2 * gap)//i每组归并的起始位置{int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n)//不用归并了{break;}if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}if (a[begin2] <= a[begin1]){tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);tmp = NULL;
}

6,基数排序

1，统计相同元素出现的次数

2，根据统计的结果将序列回收到原数组中。

数组a中的数据与count数组直接映射。

这种情况是在数据较小的情况下，如果数据较大，比如101，100，105，102，103，102这组数据，就需要开辟空间为105的数组，消耗太大了。所以可以实现一种相对映射 。

101，100，105，102，103，102以这组数据为例，找出最大与最小，就可以确定出需要开辟的数据个数：range=最大值—最小值+1；映射时count[a[i]-min]++,这样就实现了相对映射，a[i]与count数组中的a[i]-min位置映射。

代码实现：

//计数排序
void CountSort(int* a, int n)
{int max = a[0], min =a[0];//找出最大，最小for (int i = 1; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}//需开辟的数据个数int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}for (int i = 0; i < n; i++){count[a[i] - min]++;//相对映射}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;//重新放回a中}}free(count);count = NULL;
}

时间复杂度O(max(N,range))