插入排序其实我们都并不陌生
我们玩扑克牌比如斗地主的时候，整理牌的时候用的就是插入排序
现在给我们一个无序的数组，如何实现插入排序呢
首先一个元素肯定是有序的，我们就认为数组的第一个元素有序
然后数组的第二个元素数组往前面有序的部分插入元素，让前面有序的部分仍保持有序
如下图，先把5插到3后面，3,5就有序了
然后再把第三个元素1插到3前面，1,3,5也有序了
如此反复，直到把最后一个元素插入，整个数组就有序了
思想并不难理解，我们写代码的时候就可以定义end指向数组有序部分的末端，tmp变量存储要插入的值
将tmp与a[end]比较,如果tmp<a[end]，说明tmp还要继续往前走
就将a[end+1]=a[end]
直到tmp>=a[end]，说明tmp就改在此位置之后插入了
于是我们就让a[end+1]=tmp，完成插入
插入分为两种情况，一是在中途tmp>=a[end]，提前结束循环
二是end到头仍未发现比tmp大的值，此时end=-1,我们就将tmp插入到a[0],也满足a[end+1]=tmp.
以上是一次循环的过程
我们让end从0到n-2（n为数组长度），为什么end不到n-1也就是为数组最后一个元素呢
很简单，因为end后面还需要有一个待插入的元素tmp，所以end从0到n-2
稳定性：稳定
时间复杂度：最好O（N）（有序），最差O（N2）（逆序）
空间复杂度：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;
}
}
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
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;
}
}
}
稳定性：不稳定，这里很容易误以为是稳定的，因为想着只要从后往前找最大值，然后严格大于才作为max与right交换，就可以不改变相对顺序，但其实这是错的
因为你不确定你right位置的值和max位置的值交换了后会不会改变和right位置的值相等的的值和right的相对顺序
**时间复杂度：O(N2)7
空间复杂度：O（1）
void SelectSort(int* a, int n)
{
int left = 0,right=n-1;
while (left < right)
{
int minIndex = left, maxIndex = left;
for (int i = left;i <= right; i++)
{
if (a[i] < a[minIndex])
{
minIndex = i;
}
if (a[i] > a[maxIndex])
{
maxIndex = i;
}
}
Swap(&a[left], &a[minIndex]);
//如果left和maxIndex重合，left换了会导致maxIndex不指向最大值改变，要修正
if (left == maxIndex)
{
maxIndex = minIndex;
}
Swap(&a[right], &a[maxIndex]);
left++;
right--;
}
堆排序可以看我之前的博客：从二叉树到堆排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
exchange = 1;
}
}
if (exchange==0)
{
break;
}
}
}
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
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]);
}
int meeti = right;
Swap(&a[keyi], &a[meeti]);
return meeti;
}
int PartSort2(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int key = a[left];
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];
}
//相遇为坑，将key放入最后的坑
a[right] = key;
return right;
}
int PartSort3(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left, prev = left, cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int meeti = PartSort3(a, begin, end);
QuickSort(a, begin, meeti - 1);
QuickSort(a, meeti + 1, end);
}
int GetMidIndex(int* a, int left, int right)//三数取中优化快排
{
int mid = (left + right) >> 1;
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 (left > right)
{
return left;
}
else
{
return right;
}
}
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if (end - begin > 10)
{
int meeti = PartSort3(a, begin, end);
QuickSort(a, begin, meeti - 1);
QuickSort(a, meeti + 1, end);
}
else
{
HeapSort(a + begin, end - begin + 1);
}
}
void quick_sort(int* a,int left,int right)
{
if(left>=right) return;
int mid=rand()%(right-left+1)+left;
swap(&a[left],&a[mid]);
int val=a[left];
int cur=left,prev=left,end=right;
while(cur<=end)
{
if(a[cur]==val) cur++;
else if(a[cur]<val)
{
swap(&a[prev],&a[cur]);
prev++;
}
else
{
swap(&a[end],&a[cur]);
end--;
}
}
quick_sort(a,left,prev-1);
quick_sort(a,end+1,right);
}
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, left, right);
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi-1);
}
if (right > keyi + 1)
{
StackPush(&st, keyi+1);
StackPush(&st, right);
}
}
StackDestroy(&st);
}
void _MergeSort(int* a, int left, int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) >> 1;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, 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++];
}
//归并完成以后，拷贝回到原数组
memcpy(a + left, tmp + left, sizeof(a[0])*(right - left+1));
/*for (int j = left; j <= right; j++)
{
a[j] = tmp[j];
}*/
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(a[0]) * n);
if (tmp == NULL)
{
perror("malloc");
exit(-1);
}
_MergeSort(a, 0, n - 1,tmp);
free(tmp);
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(a[0]) * n);
if (tmp == NULL)
{
perror("malloc");
exit(-1);
}
int gap = 1;
while (gap < n)
{
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;
int left = begin1, right = end2;
//如果第二个区间不存在，或者第一个区间不够gap个，就不进行归并
if (begin2 >= n)
{
break;
}
//如果第二个区间存在，但是不够gap个，调整区间大小
if (end2>=n)
{
right=end2 = n - 1;
}
int j = left;
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++];
}
//归并完成以后，拷贝回到原数组
memcpy(a + left, tmp + left, sizeof(a[0]) * (right - left + 1));
}
gap *= 2;
}
free(tmp);
}
void CountSort(int* a, int n)
{
int i,j,min = 0,max=0;
for (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*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
if (count == NULL)
{
perror("malloc");
exit(-1);
}
for (i = 0; i < n; i++)
{
count[a[i] - min]++;
}
j = 0;
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i+min;
}
}
free(count);
}