学习过经典的冒泡排序算法后，我们将继续深入学习，了解更多算法排序
直接插入排序其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，指导所有记录插入完为止，得到一个新的有序序列。
特点总结：
1.元素集合越接近有序，直接插入算法的时间效率越高
2.时间复杂度是：O(N^2)
3.空间复杂度:O(1),这是一种稳定的排序算法
4.稳定性:稳定
代码实现
InsertSort(int* a,int n)
{
for(int i=0;i
int end=i;
int tmp=a[end+1];
while(end>=0)
{
if(tmp
a[end+1]=a[end];
end--;
}
else
break;
}
a[end+1]=tmp;
}
}
希尔排序（缩小增量排序）
希尔排序的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成各组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序，重复上述操作，直到gap=1时，所有记录在统一组内排好序
希尔排序的特点总结
1.希尔排序是对直接插入排序的优化
2.当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，是直接插入排序，数组已经接近有序的，性能进行优化
3.希尔排序的时间复杂度不确定，因为gap的值不确定
代码实现
void ShellSort(int* a,int n)
{
int gap=n;
while(gap>1)
{
gap=gap/3+1;
for(int i=0;i
int end=i;
int tmp=a[end+gap]
while(end>=0)
{
if(tmp
a[end+gap]=a[end];
end-=gap;
}
else
break;
}
a[end+gap]=tmp;
}
}
}
选择排序
基本思想：每一次从待排序的数据元素中选出最小（或者最大）的一个元素，存放在序列的起始位置，直到全部数据元素排序完成
直接选择排序直接选择排序的特性总结
1.容易理解，但效率不高，实际中很少使用
2.时间复杂度O(N^2)
3.空间复杂度O(1)
4.稳定性：不稳定
代码实现
void Swap(int* p1,int* p2)
{
int tmp=*p1;
*p1=*p2;
*p2=tmp
}
void SelecSort(int* a,int n)
{
assert(a);
int begin=0;
int end=n-1;
while(begin
int mini=begin
int maxi=end;
for(int i=begin+1;i<=end-1;i++)
{
if(a[i]a[maxi])
maxi=i;
}
Swap(&a[begin],&a[mini]);
if(begin==maxi)
maxi=mini;
Swap(&a[end],&a[maxi])
begin++;
end--;
}
}
堆排序
堆排序是指利用堆这种数据结构设计的排序算法，是选择排序算法的一种。排升序要建大堆，排降序要建小堆
堆排序的特性
1.使用堆排序，效率高
2.时间复杂度：O(N*logN)
3.空间复杂度：O(1)
4.稳定性：不稳定
代码实现
void AdjustDown(int* a,int size,int parent)
{
int child=parent*2+1;
while(child
if(child+1a[parent])
{
Swap(&a[child,&a[parent])
parent=child;
child=parent*2+1;
}
else
break;
}
}
void HeapSort(int* a,int n)
{
for(int i=(n-1-1)/2;i>=0;i++)
{
Adjustdown(a,n,i);
}
int end=n-1;
while(end>0)
{
Swap(&a[0],&a[end]);
AdjustDown(a,end,0);
end--;
}
}
交换排序
基本思想：比较两个记录在序列的值，再进行对换。特点是：将较大的值向尾部移动，将较小的值向头部移动。
冒泡排序特性总结：
1.时间复杂度：O(N^2)
2.空间复杂度: O(1)
稳定性：稳定
代码实现
void BubbleSort(int* a,int n)
{
assert(a);
for(int i=0;i
int exchange=0;
for(int j=1;j
if(a[j-1]>a[j])
{
Swap(&a[j-1],&a[j]);
exchange=1;
}
}
if(exchange==0)
break;
}
}
快速排序
基本思想：取一元素为基准值，将该待排序序列分为两个子序列，左序列的值小于基准值，右序列大于基准值，重复该过程直至排序完成。
一般建议：左边做基准值，右边先走
右边做基准值，左边先走
目的是为了，一趟排序后，大的值都在右边，小的值都在左边
有一个基本构架
递归的思想
void QuickSort(int array[],int left,int right)
{
if(right-left<=1)
return ;
int keyi=PartSort(array,left,right);//分左右两部分
QuickSort(array,left,mid);//递归排
QuickSort(array,mid+1,right);//递归排
}
其中将序列分为左右两部分的函数有三种方法
1.hoare法
基本思想：
定准keyi后，从右开始找小，找到小停，然后从左开始找大，找到后交换两个值，直到左右相遇
int PartSort1(int* a,int begin,int end)
{
int left=begin,right=end;
int keyi=left;
while(left
while(left=a[keyi])
{
right--;
}
while(left
left++;
}
Swap(&a[left],&a[right]);
}
Swap(&a[keyi],&a[left]);
keyi=left;
return keyi;
}
2.挖坑法
基本思想：
找到基准值后，假设为坑位，先从右边开始找小，找到小的时候，将小的值放入坑位，坑位更新。然后从左边找大，找到大的值时，放入坑位，坑位更新。直到左右相遇，此时坑中放入基准值。
int PartSort2(int* a,int begin,int end)
{
int key=a[begin];
int piti=begin;
while(begin
while(begin=key)
{
end--;
}
a[piti]=a[end];
piti=end;
while(begin
begin++;
}
a[piti]=a[begin];
piti=begin;
}
a[piti]=key;
return piti;
}
3.前后指针法
基本思想：
定义基准值和前后指针，cur先走，判断cur的值是否小于key，小于的话，prev++，当cur大于key,prev不动，cur++,当遇到cur的值小于key,交换cur,prev.当cur越界时，交换key,prev.
int PartSort3(int* a,int begin,int end)
{
int keyi=begin;
int prev=begin;
int cur=begin+1;
while(cur<=end)
{
if(a[cur]
Swap(&a[cur],&a[keyi]);
}
cur++;
}
Swap(&a[prev],&a[keyi]);
keyi=prev;
return keyi;
}
以上是递归的三种方法，还有一种非递归方法，要用到栈。
void QuickSortNonR(int* a,int begin,int end)
{
ST st;
StackInit(&st);
StackPush(&st,end);
StackPush(&st,begin);
while(!StackEmpty(&st))
{
int left=StackTop(&st);
StackPop(&st);
int right=StackTop(&st);
StackPop(&st);
int keyi=PartSort1(a,left,right);
if(left
StackPush(&st,keyi-1);
StackPush(&st,left);
}
if(right>keyi+1)
{
StackPush(&st,right);
StackPush(&st,keyi+1);
}
}
StackDestroy(&st);
}
归并排序快排特性总结
综合性能比较好
时间复杂度：O(N*logN)
空间复杂度:O(logN)
稳定性：不稳定
基本思想：采用分治法，先分解，两两有序合并，最终合并成一个有序序列。
代码实现
void _MergeSort(int* a,int begin,int end,int* tmp)
{
if(begin>=end)
return ;
int mid=(begin+end)/2;
_MergeSort(a,begin,mid,tmp);//分治递归，让子区间有序
_MergeSort(a,mid+1,end,tmp);
//开始归并
int begin1=begin,end1=mid;
int begin2=mid+1,end2=end;
int i=begin1;
while(begin1<=end1&&begin2<=end2)
{
if(a[begin1]
tmp[i++]=a[begin1++];
}
else
{
tmp[i++]=a[begin2++];
}
}
while(begin1<=end1)
{
tmp[i++]=a[begin1++];
}
while(begin2<=end2)
{
tmp[i++]=a[begin2++];
}
memcpy(a+begin,tmp+begin,(end-begin+1)*sizeof(int));
}
void MergeSort(int* a,int n)
{
int* tmp=(int*)malloc(sizeof(int)*n);
if(tmp==NULL)
{
printf("malloc failn");
exit(-1);
}
_MergeSort(a,0,n-1,tmp);
free(tmp);
}
以上是归并的递归思想，还有非递归的做法
这是偶数个的情况，当出现奇数个的情况会出现越界的情况
打印数组下标就可以看到，此时并未进行修正边界的操作，此时可以发现，end1,begin2,end2都有可能越界。
可以采用修正边界
还可以采用越界的部分不归并，但要注意边界问题，以免遗漏
最终代码实现
void MergeSortNonR(int* a,int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf("malloc failn");
exit(-1);
}
int gap = 1;
while (gap < n)
{
printf("gap=%d->", gap);
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
printf("[%d,%d] [%d,%d]--", begin1, end1, begin2, end2);
int m = end2 - begin1 + 1;
int j = begin1;
while (begin1 <=end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <=end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <=end2)
{
tmp[j++] = a[begin2++];
}
printf("n");
memcpy(a + i, tmp + i, sizeof(int) * m);
}
gap *=2;
}
free(tmp);
}
计数排序
补充一个非比较排序，计数排序
特性总结
1.在数据范围集中时，效率高。
局限性：1.浮点数，字符串不能使用 2.数据范围大，分散的话，空间复杂度高
操作步骤：
1.统计相同元素出现次数
2.根据统计的结果将序列回收到原来的序列中
代码实现
void CountSort(int* a, int n)
{
int min = a[0], 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;
int* count = (int*)calloc(range,sizeof(int));
if (count == NULL)
{
printf("calloc failn");
exit(-1);
}
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int j = 0;
for (int i = 0; i
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
}
for(int i=0;i
while(count[i]--;
{
a[j++]=i+min;
}
}
free(count);
}
复杂度分析表
稳定性就是几个相同的数字排完序后，相对位置的改变大不大。
目前常见排序算法就到此结束了，后续会更新一些细节。
