排序：
1.插入排序和希尔排序
//插入排序 时间复杂度O(N*N) 空间复杂度O(1)
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++) {
//单次插入
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
//希尔排序 时间复杂度O(N^1.2~1.3) 空间复杂度O(1)
void ShellSort(int* a, int n)
{
int gap = n;
//gap等于1时最后完整排序
while (gap > 1) {
gap = gap / 3 + 1;//保证gap最后为1
//gap间距排序
for (int i = 0; i < n - gap; i++) {
//部分排序
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;
}
PrintArray(a, n);
}
}
2.选择排序和堆排序
//选择排序 每次选一个最小 时间复杂度O(N*N) 空间复杂度O(1)
//双向选择排序 每次选出最大最小的
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = end;
int maxi = begin;
//区间遍历,找最大最小的下标
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
//注意：begin maxi重合
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
//堆排序 时间复杂度O(N*logN) 空间复杂度O(1)
//向下调整O(logN)
void AdjustDown(int* a, int n, int root)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
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--;
}
}
3.冒泡排序
//冒泡 时间复杂度O(N*N) 空间复杂度O(1)
void BubbleSort(int* a, int n)
{
int end = 0;
while(end < n-1)
{
int flag = 1;//已经有序的时候小优化
for (int i = 1; i < n - end; i++)
{
if (a[i-1] > a[i])
{
Swap(&a[i], &a[i - 1]);
flag = 0;
}
}
if (flag)
{
break;
}
end++;
}
}
4.快速排序
//快速排序 三数取中法 时间复杂度O(N*logN) 空间复杂度O(logN)
没有三数取中 最坏逆序情况下 时间复杂度O(N*N) 空间复杂度O(N)
int PartSort(int* a, int begin, int end)
{
//挖坑法
int key = a[end];
while (begin < end)
{
while (begin < end && a[begin] <= key)
begin++;
a[end] = a[begin];
while (begin < end && a[end] >= key)
end--;
a[begin] = a[end];
}
a[end] = key;
return end;
}
int PartSort2(int* a, int begin, int end)
{
//前后指针法
int cur = begin;
int prev = begin - 1;
int keyIndex = end;
//cur找比key小的，满足进行prev++然后再交换，否则继续向下找小的
while (cur < end)
{
//优化：prev++等于cur，就不用交换
if (a[cur] < a[keyIndex] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
//交换key位置
Swap(&a[cur], &a[++prev]);
return prev;
}
void QuickSort(int* a, int left,int right)
{
if (left >= right)
return;
int div = PartSort2(a, left, right);
QuickSort(a, left, div - 1);
QuickSort(a, div + 1, right);
//区间小于等于10 直接用插入排序
//else
//{
// Insert(a+left,right-left+1);
//}
}
//非递归实现
//非递归优点：1.可以减少递归带来的栈帧消耗
2.非递归用自定义栈来把数据存入堆中G单位，栈中往往是M单位（防止栈溢出）
//非递归
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
//入栈顺序
int begin = left;
StackPush(&st, begin);
int end = right;
StackPush(&st, end);
while (!StackEmpty(&st))
{
end = StackTop(&st);
StackPop(&st);
begin = StackTop(&st);
StackPop(&st);
//[begin,end]
int div = PartSort2(a, begin, end);
//[begin,div-1] div [div+1,end]
if (begin < div - 1)
{
StackPush(&st, begin);
StackPush(&st, div-1);
}
if (div + 1 < end)
{
StackPush(&st, div + 1);
StackPush(&st, end);
}
}
StackDestory(&st);
}
5.归并排序
区间：[begin,mid] [mid+1, end]
如果是：[begin, mid-1] [mid,end]会出现下图的无限递归
//归并排序 时间复杂度O(N*logN) 空间复杂度O(N)
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;
//[begin,mid] [mid+1,end]闭区间
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 index = begin;//tmp数组从begin开始
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
if (a[begin2] <= a[begin1])
{
tmp[index++] = a[begin2++];
}
}
//剩余的数据拷贝到tmp
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
//把tmp排好序的数据拷贝到原数组里面
for (int i = begin; i <= end; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
}
归并排序（非递归）：注意：区间边界把控，gap间距
//归并排序非递归
//合并区间
void MergeArr(int*a,int begin1,int end1,int begin2,int end2,int* tmp)
{
int left = begin1, right = end2;//存一下tmp区间
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
//剩余的数据拷贝到tmp
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
//拷贝到原数组里面
for (int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
int gap = 1;
//gap<n 否则区间会漏掉数据
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i,i+gap-1] [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
//边界
//1.第二段区间不存在，不用合并直接跳过
if (begin2 >= n)
break;
//2.第二段区间存在，超过n需要修正边界
if (end2 >= n)
end2 = n - 1;
//合并区间
MergeArr(a, begin1, end1, begin2, end2, tmp);
}
//PrintArray(a, n);
gap *= 2;
}
}
外排序：1000万文件排序，可以把1000万数据分成100份，每一份10万个数据进行快速排序后，利用归并的思想100份文件在外存中两两归并（或前一个文件与后一个归并有序后，再去和下一个文件归并）
6.计数排序
//计数排序 时间复杂度O(n+gap) 空间复杂度O(gap)
void CountSort(int* a, int n)
{
//找出数组中最大最小值
int min = a[0];
int max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//开辟用来计数的数组
int gap = max - min + 1;
int* count = (int*)malloc(sizeof(int) * gap);
if (count == NULL)
printf("内存不足");
//计数数组初始化为0
memset(count, 0, sizeof(int)*gap);
for (int j = 0; j < n; j++)
{
//计数+1
count[a[j] - min]++;
}
//计数后拷贝到原数组
int index = 0;
for (int i = 0; i < gap; i++)
{
while (count[i] > 0)
{
a[index++] = i + min;
count[i]--;
}
}
}
