排序的概念
1.概念
就我当前所认识的排序来说。排序是把一串相同类型的数据，按照升序或者降序排列起来的操作。
以下介绍的排序大多可以排列不限于整型和文件，但也有一些算法有较明显的局限性。
2.稳定性
如果在排列之前，一组数据中，相同的数据A在B前面，排序后A仍然在B前面，则说明这样的算法是稳定的。如果不是这样，那么这样的算法是不稳定的。
3.内部排序和外部排序
内部排序：数据元素在内存中进行的排序。
外部排序：数据元素太多，根据排序的过程不能在内外存之间移动的排序。
常见的排序算法
1.直接插入排序
思想
（以升序为例）第一次从数据中拿最前面的数放到第一个，再从数据中拿第二个数，放置时和第一个数比较，比它大放后面，比它小放前面。后面的数再和已经有序的数组中最后一个比，比它小再往前依次比，直到找到比手中的数更小的数，就放它后面了。
特点
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O（N²） 【是O（N²）中最能打的】
空间复杂度：O（1），它是一种稳定的排序算法
稳定性：稳定
关于这个排序稳定性的说明，它取数是依次取的，就算值相等，那么先取的在前面，后取的在后面，根本不会改变相同值的位次。所以它是稳定的。
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)//
{
int end = i;
int tmp = arr[end + 1];//用tmp来记住下一个待比较的数
while (end >= 0)//end 和tmp比较
{
if (tmp < arr[end])
{
arr[end+1] = arr[end];//如果tmp小，那么end往tmp的位置挪，tmp和前一个位置比
end--; //end减减才能和前一个位置比
}
else
{
break; //如果tmp大，直接跳出来
}
}
arr[end+1] = tmp;//tmp插入到比它小的数后面
}
}
2.希尔排序
希尔排序法又称为缩小增量法。基本思想：选定一个整数gap，把待排序的N个数据，分成N/gap个组。每组gap个，以gap为间隔。第一次把这N/gap个组进行直接插入排序。第二次是间隔 N/gap/gap。以此类推，当这个分母越大，逼近于N时，间隔就越小，间隔趋近于1，整体越发有序，当gap=1时，就是有序排序了。
所以希尔排序是要排很多趟的，越有序，越简单。
特点
时间复杂度 O（N*log（N））；
空间复杂度 O(1);
void ShellSort(int* arr, int n)
{
int gap = n; //把n给gap，这样n就不用改变了，待会方便它自己÷
while (gap>1)
{
gap = gap/3 +1; //gap就是间隔，+1防止它变成0，并且保证最后一定是1，那么前面的while条件就要给跳出条件。
for (int i = 0; i < n - gap; i++)//先排1 gap gap+gap。。。再排2 2+gap。。这样一个for循环就解决了
{
int end = i;
int tmp = arr[end + gap];//用tmp来记住下一个待比较的数
while (end >= 0)//end 和tmp比较
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];//如果tmp小，那么end往tmp的位置挪，tmp和前一个位置比
end-=gap; //end减减才能和前一个位置比
}
else
{
break; //如果tmp大，直接跳出来
}
}
arr[end + gap] = tmp;//tmp插入到比它小的数后面
}
}
}3.选择排序
思想
从待排序的数中每次挑一个最大的，一个最小的排在数组的第一个和最后一个位置。直到选完。
特点
时间复杂度O（N²）
空间复杂度O（1）
稳定性：不稳定。
void SelectSort(int* a, int n)
{
for (int min = 0, max = n - 1; min <= max; min++, max--)
{
for (int i = min+1; i < n-min; i++)
{
if (a[min] > a[i])
{
swap(&a[min], &a[i]);
}
if (a[max] < a[i])
{
swap(&a[max], &a[i]);
i--;
}
}
}
}
4.堆排序
思想
把数组进行向下调整，形成一个大堆。把堆顶的数换到数组最后一个位置，再把整个数组size--，使这个数不再参与接下来的排序。每调整一个数，就要进行一次向下调整。这样，数组从后向前开始变得有序。直到堆里不再有数。那么整个数组就算完全有序了。
特点
时间复杂度：O(N*log(N));
空间复杂度：O(1);
稳定性：不稳定；
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = 2 * parent + 1;
while (child < n)
{
if (child+1<n && a[child] < a[child+1])
{
child++;//左孩子和右孩子之间存在紧密联系，所以不能新建一个值来表示更小的那个，那样会导致交换难以进行
}
if ( a[child] > a[parent])//如果孩子小于父亲，交换
{
swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//向下调整建堆
for (int i = (n - 1 -1) / 2; i >= 0; i--)//从最后一颗子树开始调，最后一棵树的下标是n-1,（n-1-1)/2就是最后一棵子树的根节点，
{
AdjustDwon(a,n, i);
}
//堆排序
int end = n - 1;
while (end>0)
{
swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}5.冒泡排序
思想
数组第一个数和第二个数比，大的往后，然后第二和第三比，大的往后，走一趟确定一个最大的数，然后排剩下的，把剩下的中最大的排在倒数第二。然后接着排，直到排完。
特点
时间复杂度O(N²）
空间复杂度O（1）
稳定性：稳定
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int flag = 0;
for (int j = 0; j < n - i-1;j++)
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = 1;
}
}
if (!flag)
{
break;
}
}
}6.快速排序
思想
选择一个key，一般选最左边的数。然后定义左下标和右下标。左下标从0开始，右下标从最后一个数开始。右下标找比key小的数，找到了后左下标找比key大的数，找到了就和右下标的数进行交换。当两人相遇时，左下标就和key所在的数进行交换。这样key把整个数组分为比key小的数和比key大的数。利用递归，把比key小的这组数照这种方式排，比key大的这组数也这样排。相当于一个前序的遍历了。排完以后就有序了。
特点
时间复杂度O（N*log(N))
空间复杂度O（logN）
稳定性：不稳定
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
if (a[right] < a[keyi])
{
if (a[left] > a[keyi])
{
swap(&a[left], &a[right]);
}
else
{
left++;
}
}
else
{
right--;
}
}
swap(&a[keyi], &a[left]);
return left;//此时left将数组划分为两个地盘
}
快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int keyi = left;
int key = a[left];
while(left < right)
{
if (a[right] < key)
{
swap(&a[right], &a[left]);
while (left < right)
{
if (a[left] > key)
{
swap(&a[right], &a[left]);
break;
}
else
{
left++;
}
}
}
else
{
right--;
}
}
return left;
}
int Getmidindex(int* a, int left, int right)
{
assert(left < right);
int mid = (left + right) / 2;
// 对三个值进行排序，确保a[left] <= a[mid] <= a[right]
if (a[left] > a[mid])
swap(&a[left], &a[mid]);
if (a[left] > a[right])
swap(&a[left], &a[right]);
if (a[mid] > a[right])
swap(&a[mid], &a[right]);
return mid;
}
int PartSort3(int* a, int left, int right)
{
//后指针找小，前指针不用找，找到了两人交换
int mid = Getmidindex(a, left, right);
int keyi = left;
swap(&a[mid], &a[keyi]);//交换以后a[keyi]就是最合适的数了。
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && a[++prev] != a[cur])//cur小于key，再把prev++，如果等于cur，不执行。
swap(&a[prev], &a[cur]);//如果连续是小，那么最后只能用最后一个小和key交换，然后还要再排一遍。
cur++;
}
swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
if (right - left <= 1)
{
return;
}
int div = PartSort3(a, left, right);
QuickSort(a, left, div);
QuickSort(a, div + 1, right);
}非递归要用到栈
void QuickSortNonR(int* a, int left, int right) {
Stack st;
StackInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
left = StackTop(&st);
StackPop(&st);
right = StackTop(&st);
StackPop(&st);
int div = PartSort3(a, left, right);
if (div + 1 < right)
{
StackPush(&st, right);
StackPush(&st, div + 1);
}
if (left < div-1 )
{
StackPush(&st, div-1);
StackPush(&st, left);
}
}
StackDestroy(&st);
}7.归并排序
思想
把数两两分组，然后排序。排好后返回，然后四个四个排，然后八个八个排。这是递归。
合并的思想是创建一个新的数组，这两两分组，就有两个数组。分别设置好两组的下标。两个坐标的第一个数依次比较，谁小就把谁插入到新数组中。最后再把有序的新数组的数复制到之前的数组。
存在的问题是并不是所有数组都是以2、4、8的倍数生成的。因此可能会发生数组越界的问题，那么就要进行修正。当最后剩下的数不再是倍数，就直接复制回原来的数组，参与下一次的排序。
特点
时间复杂度：O（N*log（N））
空间复杂度：O（N）
稳定性：稳定
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)//如果只有一个数或者没有数，返回，不比
{
return;
}
int mid = (begin + end) / 2;
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int index = begin;//用于新建的空间的下标。
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
while (begin1 <= end1 && begin2 <= end2)//当遵守游戏规则的时候，开始比较
{
if (a[begin1] <= a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while(begin1 <=end1)//begin1里面还有数，就说明begin2没数了，把begin1的数全放进去
tmp[index++] = a[begin1++];
while(begin2 <=end2)
tmp[index++] = 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)
{
perror("malloc failed!");
exit(1);
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc failed!");
exit(1);
}
int gap = 1;
while (gap < n)
{
//两两归并，然后以2的倍数再排再归并，多出的数要修正，不进入，直接复制
for (int i = 0; i < n; i +=2*gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i+(gap * 2) - 1;
//修正区间
if (end1 >= n)
{
end1 = n - 1;
}
if (begin2 >= n)
{
begin2 = n;
end2 = n-1;
}
if (begin2 < n && end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while (begin1 <= end1)//begin1里面还有数，就说明begin2没数了，把begin1的数全放进去
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
free(tmp);
}8.计数排序（非比较排序）
思想
按照数组的特点，先遍历一遍数组，选出最大的数和最小的数。生成一个这个范围的新的数组。然后再把数往计数数组里放，出现一次的对应新数组储存的数就+1.两次就加2，最后一步，从计数数组中依次取数。
特点
时间复杂度O（N或者range)
空间复杂度O（range）
稳定性：稳定
只能用于整型
void CountSort(int* a, int n)
{
int min = a[0];
int max = a[0];
for (int i = 1; i < n; i++)
{
if (min > a[i])
{
min = a[i];
}
if (max < a[i])
{
max = a[i];
}
}
//知道范围以后可以开空间了
int range = max - min + 1;
int* countmp = (int*)malloc(sizeof(int) * range);
assert(countmp);
memset(countmp, 0, sizeof(int) * range);//初始化为0
for (int i = 0; i < n; i++)
{
countmp[a[i] - min]++;//读一个数，这个数对应的countmp的数字就++
}
int j = 0;
for (int i = 0; i < range; i++)
{
while (countmp[i]--)
{
a[j++] = i+ min;
}
}
free(countmp);
}
