目录
前言
一、插入排序
二、希尔排序
三、选择排序
四、堆排序
五、冒泡排序
六、快速排序
七、归并排序
八、计数排序
九、稳定性
前言
此篇博客都是以升序为例，降序只需更改部分地方即可，所以只排一个
一、插入排序
单趟排序
如上图，在一个有序数组中插入一个6，只要找到比6小的数，此数后面的数往后挪动，然后在其后插入6即可
整个插入排序
外面只需套一层循环即可，为了保证不越界，所以i最多只能是倒数第二个元素的下标
如上图，起初可将第一个数看成是有序的，第二个数就是待插入的数，比它小就往前放，比它大就跳出循环，然后就是前2个数有序、前三个数有序……前n-1个数有序等等
二、希尔排序
希尔排序是在插入排序的基础上加强的
核心思路就是先分组，然后让每一组的数据都有序，最后再插入排序即可
设gap=3，即分3组
单趟排序与插入排序类似，只是把+1/-1改为了+gap/-gap，下图是第一组的排序
如下图，外面套一层for循环，就能把其它组进行排序了，循环判断条件n-gap,保证还留一组在外，i取不到，是为了保证不会越界，while循环是为了进行多次预排，gap=1时，就是插入排序
(也能不要while循环，直接将gap赋初值为3或其它数)
三、选择排序
如上图，采用的是头尾双指针，头指针找小，尾指针找到，然后两者交换即可
如上图，最后面加一个if语句是为了防止第一个数就是最大数，会被换走
四、堆排序
首先得写一个向下调整的函数(向上调整也行)
因为是排升序，所以建大堆比较好
因为大堆根节点是最大的数，所以将其与最后一个数交换，然后将n-1个数向下调整又成为一个新的大堆，多次如此即排序完成，当只有一个数时，就不需要排了，因为它是第一个数，也是最小的数，后面的数都是有序数组了
五、冒泡排序
单趟排序
两个数比较大小，小的就放前面，大的放后面，往后如此，最大的数就放在最后了
整个排序
再往外套一个循环，有n个数，就得走n-1趟，而每一趟比较的次数也是逐渐-1
定义一个变量flag，赋初值为1,表示假设它有序，当有比较交换时就赋值为0，表示无序，当走完一趟，flag还是1，就表示有序了，直接break跳出循环，结束排序即可，所以flag能提高效率
六、快速排序
hoare版本
首先创建左右两个指针，选左边作key，右边先走，右指针找小于指向key的值，左指针找大于指向key的值，当两个指针相遇时结束，然后将指向key的值与相遇指向的哪个值交换，这样key指向的值，左边都小于它，右边都大于它，最后返回相遇的下标(右边作key，左边先走)
有=是因为当数组的数据全是同一个数时会死循环
要加left<right是防止越界，如5 4 3 2 1时，left就会一直+，从而越界
如果左边作key，左边先走，就会出问题，如下图
挖坑法
左边选key，还是右边先走，这次key是左边的第一个元素而不是下标，而坑位则是下标，起初是第一个元素的下标，当right遇到小时，就把该坐标的值赋值给坑位所在的数组成员，而该坐标则是新的坑位，同理，left也一样，left与right相遇结束，然后把key赋值给坑位所在的数组成员即可
前后指针法
选左做key，定义两个指针cur和prev，cur在前，prev在后，cur找小于key指向的数据，当cur指向的数值一直为小时，prev就一直紧跟着，二者不发生交换，当二者经过了有比key指向的数据大时，再遇到小于key指向的数据时，才发生交换，当cur指向的数据不再是数组中的数据时结束，最后将prev指向的数据与key指向的数据交换
整个排序(递归)
把一大区间的排序分成多个左右小区间来排序，当只有left>=right时就结束
整个排序(非递归)
得借助栈来保存区间的两个端点
首先先存储开始大区间的两个端点
因为栈是后进先出，所以先用begin存储先出来的数据，用end存储后出来的数据
然后就可以调用函数找keyi了
此时就能分成两个区间，一个是[begin,keyi-1],另一个是[keyi+1,end],然后再把这两个区间的端点都放到栈中去，再取出即可
循环判断条件是栈中是否还有数据，即栈是否为空，最后销毁栈即可
快速排序优化
可以从左中右三个位置取出中间大小的数，然后与左边的数交换，再选左做key，能使其分为相对均衡的两个小区间，提高效率，比如数组是1 4 7 3 5 2 8 6 9，排升序
七、归并排序
借助一个临时数组，将原数组分为2个区间，看成两个有序数组，再将其按照从小到大的顺序拷贝到临时数组中，而想要是有序数组，需要不断缩小区间，直到2个区间都各只有一个数时，就拷贝到临时数组中去，如下图
取中间坐标，将其化为小区间，再分别递归
两个区间从起始端点开始，逐渐比较大小，当有一个区间被拷贝完就结束循环
还有一个区间没拷贝完，所以仍需接着拷贝
拷贝完后，还需拷贝回原数组，因为需要从原数组中拿数据
如上图，一一归并后临时数组是2 4 3 7 1 6 9 11，原数组是4 2 3 7 6 1 9 11
两两归并时，两个区间都不是有序数组，就达不到目的，所以需拷贝回原数组
非递归
同样需借助临时数组
gap是分组，开始是分成n组，然后是n/2组等等，gap每次归完后是*2，如一一归完后gap就*2
一一归完后，二二归等等，所以要借助for循环，每次归完从头开始
index是拷贝到临时数组时，临时数组的下标
这里可以先每次归完后再拷贝回原数组，与递归有所差异
只有数组的数据个数和满二叉树的数据一样多时，才不会出现越界问题，所以需考虑越界
有三种越界，end1，begin2，end3越界
begin2越界时，只要使右区间不存在，就不会出现越界和后面循环重复拷贝的情形
八、计数排序
首先要从数组中找到它的最大值和最小值，从而用相对的方式来计数，不至于浪费空间，比如如果只找最大值，假如是900，最小值却是600，如果从0开始就得开辟901个数据的空间，而用下标为0存600，就只需要301个数据的空间，同时需借助临时数组，以及用memset将其全部置为0
然后计数，如600，下标为0的元素就表示600，有几个600该元素就+几，605，下标为5的元素就是605等等
从最小的数据开始取数据，有几个就取几个
九、稳定性
概念：同大小的数据在数组中的相对位置，如果发生变化就表示不稳定，没有发生变化就表示稳定
如下图，就表示不稳定
插入排序、冒泡排序、归并排序是稳定的，没有改变相对位置
而希尔排序不稳定，因为涉及分组，所以相对位置会发生变化
堆排序不稳定，如下图
选择排序也不稳定，如下图
快速排序也不稳定，如下图
计数排序不稳定
十、全部代码
void swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
void Print(int* str, int sz)
{
assert(str);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", str[i]);
}
printf("\n\n");
}
void AdjustDown(int* str, int sz, int parent)
{
int child = parent * 2 + 1;
while (child < sz)
{
if (child + 1 < sz && str[child + 1] > str[child])
{
child++;
}
if (str[child] > str[parent])
{
swap(&str[child], &str[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void InsertSort(int* str, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int end = i;
int x = str[end + 1];
while (end >= 0)
{
if (str[end] > x)
{
str[end + 1] = str[end];
end--;
}
else
{
break;
}
}
str[end + 1] = x;
}
}
void ShellSort(int* str, int sz)
{
int i = 0;
int gap = sz;
while (gap > 1)
{
gap = gap / 2;
for (i = 0; i < sz - gap; i++)
{
int end = i;
int x = str[end + gap];
while (end >= 0)
{
if (str[end] > x)
{
str[end + gap] = str[end];
end -= gap;
}
else
{
break;
}
}
str[end + gap] = x;
}
}
}
void SelectSort(int* str, int sz)
{
int left = 0;
int right = sz - 1;
int maxi = 0;
int mini = 0;
int i = 0;
while (left < right)
{
maxi = left;
mini = left;
for (i = left; i <= right; i++)
{
if (str[i] > str[maxi])
{
maxi = i;
}
if (str[i] < str[mini])
{
mini = i;
}
}
swap(&str[left], &str[mini]);
if (left == maxi)
maxi = mini;
swap(&str[right], &str[maxi]);
left++;
right--;
}
}
void HeapSort(int* str, int sz)
{
int i = 0;
for (i = (sz - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(str, sz, i);
}
int end = sz;
while (end > 1)
{
swap(&str[0], &str[end - 1]);
end--;
AdjustDown(str, end, 0);
}
}
void BubbleSort(int* str, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
int flag = 1;
for (j = 0; j < sz - 1; j++)
{
if (str[j] > str[j + 1])
{
swap(&str[j], &str[j + 1]);
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
int GetMid(int* str, int left, int right)
{
int mid = (left + right) / 2;
if (str[left] < str[right])
{
if (str[left] < str[mid])
return mid;
else if (str[left] > str[mid])
return left;
else
return right;
}
else
{
if (str[left] < str[mid])
return left;
else if (str[right] > mid)
return right;
else
return mid;
}
}
int Partion1(int* str,int left,int right)
{
int mid = GetMid(str, left, right);
swap(&str[mid], &str[left]);
int keyi = left;
while (left < right)
{
while (left < right && str[right] >= str[keyi])
{
right--;
}
while (left < right && str[left] <= str[keyi])
{
left++;
}
swap(&str[left], &str[right]);
}
swap(&str[left], &str[keyi]);
return left;
}
int Partion2(int* str, int left, int right)
{
int mid = GetMid(str, left, right);
swap(&str[mid], &str[left]);
int key = str[left];
int hole = left;
while (left < right)
{
while (left < right && str[right] >= key)
{
right--;
}
str[hole] = str[right];
hole = right;
while (left < right && str[left] <= key)
{
left++;
}
str[hole] = str[left];
hole = left;
}
str[hole] = key;
return hole;
}
int Partion3(int* str, int left, int right)
{
int mid = GetMid(str, left, right);
swap(&str[mid], &str[left]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (str[cur] < str[keyi] && cur != ++prev)
{
swap(&str[cur], &str[prev]);
}
cur++;
}
swap(&str[prev], &str[keyi]);
return prev;
}
void QuickSort(int* str,int left,int right)
{
if (left >= right)
return;
int keyi = Partion3(str, left, right);
QuickSort(str, left, keyi - 1);
QuickSort(str, keyi + 1, right);
}
void QuickSortNonR(int* str,int left,int right)
{
ST st;
STInit(&st);
STPushTop(&st, right);
STPushTop(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPopTop(&st);
int end = STTop(&st);
STPopTop(&st);
int keyi = Partion3(str, begin, end);
if (end > keyi + 1)
{
STPushTop(&st, end);
STPushTop(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPushTop(&st, keyi - 1);
STPushTop(&st, begin);
}
}
STDestroy(&st);
}
void _MergeSort(int* str, int left, int right, int* tmp)
{
if (left >= right)
return;
int mid = (left + right) / 2;
_MergeSort(str,left, mid, tmp);
_MergeSort(str, mid + 1, right, tmp);
int begin1 = left;
int begin2 = mid + 1;
int end1 = mid;
int end2 = right;
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (str[begin1] < str[begin2])
{
tmp[i++] = str[begin1++];
}
else
{
tmp[i++] = str[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = str[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = str[begin2++];
}
int j = left;
for (j = left; j < i; j++)
{
str[j] = tmp[j];
}
}
void MergerSort(int* str, int left, int right)
{
int* tmp = (int*)malloc(sizeof(int) * (right + 1));
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
_MergeSort(str, left, right,tmp);
free(tmp);
tmp = NULL;
}
void MergerSortNonR(int* str, int left, int right)
{
int* tmp = (int*)malloc(sizeof(int) * (right + 1));
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int i = 0;
int gap = 1;
while (gap <= right)
{
for (i = 0; i < right; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
int index = i;
//end1越界
if (end1 > right)
{
end1 = right;
}
//begin2越界
if (begin2 > right)
{
begin2 = end2 + 1;
}
//end2越界
if (end2 > right)
{
end2 = right;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (str[begin1] < str[begin2])
{
tmp[index++] = str[begin1++];
}
else
{
tmp[index++] = str[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = str[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = str[begin2++];
}
}
int j = 0;
for (j = 0; j <= right; j++)
{
str[j] = tmp[j];
}
gap *= 2;
}
free(tmp);
tmp = NULL;
}
void CountSort(int* str, int sz)
{
int max = str[0];
int min = str[0];
int i = 0;
for (i = 1; i < sz; i++)
{
if (str[i] > max)
max = str[i];
if (str[i] < min)
min = str[i];
}
int* count = (int*)malloc(sizeof(int) * (max - min + 1));
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int) * (max - min + 1));
for (i = 0;i < sz;i++)
{
count[str[i] - min]++;
}
i = 0;
int j = 0;
while(i < sz)
{
while (count[j]-- && j <= max - min)
{
str[i++] = min + j;
}
j++;
}
}