间接插入排序
⾸先，咱们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有⼀个元素，就是数组的第⼀个元素。插⼊算法的核⼼思维是取未排序区间中的元素，在已排序区间中找到适合的插⼊地位将其插⼊，并保障已排序区间数据⼀直有序。反复这个过程，直到未排序区间中元素为空，算法完结。
如图所示，要排序的数据是4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。
插⼊排序蕴含两种操作，⼀种是元素的⽐较，⼀种是元素的挪动。比方咱们须要将⼀个数据3插⼊
到已排序区间[1,4,5,6]时，须要拿3与已排序区间的元素6,5,4,1顺次⽐较⼤⼩，找到适合的插⼊地位。找到插⼊点之后，咱们还须要将插⼊点之后的元素程序往后挪动⼀位，这样能力腾出地位给元素3插⼊。比方3和6比拟，此时就能够将3和6的地位进行替换，顺次类推，3再和5替换，3再和4替换，当3和1比拟发现3比1大就不必再替换了，实现了3的插入过程了
C代码
include<stdio.h>
//排升序
void InsertSort( int *p,int sz){
for(int i=0; i<sz-1; i++){
int end=i;
while(end>=0){
if(p[end+1]<p[end]){
int tmp=p[end+1];p[end+1]=p[end];p[end]=tmp;
end--;
}
else{
break;}
}
}
}
int main(){
int arr[]={4,5,6,1,3,2};
int sz=sizeof(arr)/sizeof(arr[0]);InsertSort(arr,sz);
for(int i=0; i < sz;i++)i
printf( "%d " ,arr[i]);
}
printf ( "n" );return 0;输入后果：123456
工夫复杂度O(N^2),空间复杂度O(1）
稳定性：稳固
稳定性的阐明
图中红色的5在排完序后仍旧在蓝色的5前面，这就是稳固的体现
希尔排序
希尔排序能够看成是对间接插入排序的优化：咱们能够看到间接插入排序的毛病即对一个降序的数组进行升序那么工夫复杂度为O(N^2)，然而对该数组进行降序那么工夫复杂度就为O(N)了，此时大家会想该数组都是降序的了，你再对其降序图啥呢？这里想论述的观点是如果将该数组变为
靠近有序的状态那么应用间接插入排序其工夫复杂度不就降下来了吗，希尔排序就是用了这个思维
对间接插入排序进行了优化！！！
执行后果：50 60 61 70 80 83 84 87 88 99
工夫复杂度O(N^logN),空间复杂度O(1)
稳定性：不稳固
间接抉择排序
根本思维：一次挑一个数据：每一次从待排序的数据元素中选出最小（或最大）的一个元素，寄存在序列的起始地位，直到全副待排序的数据元素排完。java培训
堆排序
留神：应用堆排序首先须要了解什么是堆，大堆与小堆的区别，这里就不对堆的概念进行阐明
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是抉择排序的一种。它是通过堆来进行抉择数据。须要留神的是排升序要建大堆，排降序建小堆。
将数组key=[20,17,4,16,5,3]建设一个大堆，对该数组排升序。
如何将一个一般的数组建设成一个大堆这里就不作讲述
工夫复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳固
冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进⾏⽐较，看是否满⾜⼤⼩关系要求。如果不满⾜就让它俩调换。图中相邻的元素如果右边的元素大于左边的元素，那么就进行替换，即相邻的两个元素左边总是较大的。
工夫复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳固
疾速排序
疾速排序是Hoare于1962年提出的一种二叉树构造的替换排序办法，其根本思维为：任取待排序元素序列中 的某元素作为基准值，依照该排序码将待排序汇合宰割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，而后对左右子序列反复该过程，直到所有元素都排列在相应地位上为止。
将区间依照基准值划分为左右两半局部的常见形式有：
hoare版本
挖坑法
前后指针版本
三数取中法选key（能够保障不会呈现最坏的状况，而且当数据有序的时候就是最好的状况）
递归到小的子区间时，能够思考应用插入排序
//快排，工夫复杂度，最好的状况O(N*log2(N)),最坏O（N^2)
//优化办法1：三数取中，防止快排呈现最坏的状况
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) >> 1;//移位的效率比除以2的效率要高一点
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] >= a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}}
hoare版本
int PartSort1(int* a, int left, int right)//排序一趟就返回相遇点
{
int midIndex = GetMidIndex(a, left, right);//应用三数取中
Swap(&a[left], &a[midIndex]);//将三数取中后的后果与最右边的值进行替换
int keyi = left;
while (left < right)
{
// 找小
while (left < right && a[right] >= a[keyi])
--right;
// 找大
while (left < right && a[left] <= a[keyi])
++left;
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;//返回相遇的地位，也就是keyi}
挖坑法
int PartSort2(int* a, int left, int right)
{
int midIndex = GetMidIndex(a, left, right);//应用三数取中
Swap(&a[left], &a[midIndex]);//将三数取中后的后果与最右边的值进行替换
int key = a[left];//将最右边的值给key,而后将最右边的视为坑（没有数据的意思）
while (left < right)
{
// 找小
while (left < right && a[right] >= key)
{
--right;
}
// 放到右边的坑位中,左边就造成新的坑
a[left] = a[right];
// 找大
while (left < right && a[left] <= key)
{
++left;
}
// 放到左边的坑位中，右边就造成新的坑
a[right] = a[left];
}
a[left] = key;//最初相遇点肯定是坑，将key放到坑中
return left;//返回相遇点，也就是key值所在的地位}
前后指针版
int PartSort3(int* a, int left, int right)
{
int midIndex = GetMidIndex(a, left, right);
Swap(&a[left], &a[midIndex]);
int keyi = left;
int prev = left, cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)//cur找比keyi小的数
{
Swap(&a[cur], &a[prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
return prev;//最初返回prev的地位，也就是keyi，这里的keyi示意的是下标}
疾速排序代码
下面的都是各版本进行单趟排序的代码
void QuickSort(int* a, int begin, int end)//（用的是hoare法）
{
if (begin >= end)//[begin,end]区间为0或者区间不存在则返回
return;
// 1、如果这个子区间是数据较多，持续选key单趟，宰割子区间分治递归
// 2、如果这个子区间是数据较小，再去分治递归不太划算
//此时越往后递归，子区间就越多，每个子区间的数据就越少，每个子区间都要递归就不划算，
//能够在前面进行插入排序，因为此时每个子区间是靠近有序的，靠近于希尔排序了
if (end - begin > 0)//小区间优化的成果没那么显著，如果对相应数据量级进行针对性的调
//往往数据量越大，比方将20换成1000成果就显著了，20是官网给的，官网不敢给大了
{
int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
//int keyi = PartSort3(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
QuickSort(a, begin, keyi - 1);//递归
QuickSort(a, keyi + 1, end);//递归
}
else
{
InsertSort(a + begin, end - begin + 1);
//HeapSort(a + begin, end - begin + 1);也能够换成其如堆排，希尔排序成果会更好
}}
工夫复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳固
归并排序
归并排序（MERGE-SORT）是建设在归并操作上的一种无效的排序算法,该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用。将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
void _MergeSort(int a, int left, int right, int tmp)
{
if (left >= right)
return;
int mid = (left + right) >> 1;
// [left, mid][mid+1,right]
_MergeSort(a, left, mid, tmp);//先递归进行分治
_MergeSort(a, mid + 1, right, tmp);
// 两段有序子区间归并tmp,并拷贝回去
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
// 归并实现当前，拷贝回到原数组
for (int j = left; j <= right; ++j)
a[j] = tmp[j];}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//创立长期数组
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);}
工夫复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳固
计数排序
//计数排序
void CountSort(int* a, int n)
{
int min = a[0];//记录数组中的最小值
int max = a[0];//记录数组中的最大值
for (int i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;//min和max之间的自然数个数（包含min和max自身）
int* count = (int*)calloc(range, sizeof(int));//开拓可储存range个整型的内存空间，并将内存空间置0
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//统计雷同元素呈现次数（绝对映射）
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int i = 0;
//依据统计后果将序列回收到原来的序列中
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count);//开释空间}
工夫复杂度：O(MAX(N+范畴))
空间复杂度：O(范畴)
稳定性：稳固
发表回复