排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。
1.插入排序
void insort(int* a, int n)//插入排序
{
int i = 0;
for (i= 0; i< n-1; i++)
{
int end = i;
while (end>0)
{
if (a[end + 1] < a[end])
{
swap(&a[end + 1], &a[end]);
end--;
}
else
{
break;
}
}
}
}插入排序的操作是将一条记录插入已排好序的表，从而得到一个新的，记录加1的有序表
代码解析：
因为在代码中需要end+1和end做比较，当end==n-1时，end+1便会发生越界，所以在for循环中i<n-1。
end--能够使新插入的数据不断向前比较，使其找到合适的位置，当end<0时，便会停止循环，从下一个结点继续遍历。
2.希尔排序
希尔排序有插入排序进行该着，它会在正式排序之前先对数据进行预排序，使其时间复杂度降低。
void shellsort(int* b, int n)
{
int i = 0;
int j = 0;
int gap = n;
int end = 0;
while (gap > 1)
{
gap = gap / 3 + 1;
for (j = 0; j < gap; j++)
{
for (i = 0; i < n - gap; i += gap)
{
end = i;
while (end >= 0)
{
if (b[end + gap] < b[end])
{
swap(&b[end + gap], &b[end]);
end -= gap;
}
else
{
break;
}
}
}
}
}
}希尔排序把数据分成gap份，然后以gap为间隔将数据区分开，从而避免插入排序面对逆序数据的最坏情况，gap会逐渐缩小，间隔也会逐渐缩小。整体的数据会更加趋于有序，这个时候使用直接插入排序效率会更高。所以gap值要不断变小。
这里gap=gap/3+1能够让gap的最后一个值刚好停在了1，当gap>1时是预排序，当gap=1时，表示插入排序。
这里的j循环表示了能够区分不同组的数据，将数据分为了gap组。
这里作者使用三个循环来解决问题，在i循环中整体思路与插入排序相似，先将同一组数据先排好序，然后将切换不同组排序。
i<n-gap能够在里层的while循环的比较中避免了数组发生越界。
当排序运行到最后一次时，gap的值将变为1，在第二个for循环中将变为插入排序。
3.选择排序
选择排序是一种较为暴力的算法，它在一排数据中选出最小个的放在最左边，将最大个的放在最右边
void selectsort(int* a, int n)
{
int begin = 0;
int end = n - 1;
int i = 0;
int min=0, max=0;
while (begin < end)
{
int min = begin, max = end;
for (i = begin; i < end; i++)
{
if (a[i]<a[min])
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
swap(&a[min], &a[begin]);
if (max == begin)
{
max = min;
}
swap(&a[max], &a[end]);
begin++;
end--;
}
}选择排序的关键在于选出最小数和最大数的下标，然后在for循环之后将最小数和最大数的位置与初位置和末位置进行交换，但是在交换的时候需要注意更新数据的位置，不然排序的时候会发生意外。
由于是先将最小数进行交换，所以当max==begin时，begin的值已经与min的值进行互换，所以要将max=min
4.快速排序
1.hoare法
int aaa(int* a, int left, int right)//三数取中
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}void qusort(int* a, int left, int right)
{
if (left >= right)//数组不存在
{
return;
}
if ((right-left+1) < 10)
{
insort(a+left, right - left + 1);
}
else
{
int midi = aaa(a, left, right);
swap(&a[midi], &a[left]);
int begin = left, end = right;
int key = left;
while (begin < end)
{
while (begin < end && a[end] >= a[key])
{
end--;
}
while (begin < end && a[begin] <= a[key])
{
begin++;
}
swap(&a[begin], &a[end]);
}//循环停下表示相遇
swap(&a[begin], &a[key]);
key = begin;
qusort(a, left, key - 1);
qusort(a, key + 1, right);
}
}快速排序需要将数组的左区间和右区间传进函数中，如果函数的left>=right说明这个数组不存在
快速排序在面对数据量较小的时候应避免产生过多的栈帧，防止程序出现bug，所以我们在数据量较小的时候可以对数组使用插入排序。
如果数列有序，往往快速排序的时间复杂度便由O(nlog2n)退化到O(n ^2)，即相当于冒泡排序，此时我们就要使用三数取中，选出一个不是最大也不是最小的数，避免end不断往下走。然后让第一位的数据与midi进行交换。
当数据量较多的时候，我们从中选出一个关键字key，比key小的数据排在它的左边，数据大的排在右边，所以在函数中应左边找大，右边找小，找出来了之后对它们进行互换。
当循环停下来的时候，表明了begin与end相遇，此时的位置数据必定比key要小
相遇场景分析：
1.begin遇end:因为函数中时右边的end先走，所以当他停下来的时候它所遇到的数据必定比key要小，然后begin继续走没有发现比key要大的数，直到遇到end。
2.end遇begin:end先走，没有遇到比key要小的数，直到遇到begin，而begin停下的位置刚好是上一轮交换的位置，此时begin位置的数据必定比key小。
这时就可以将key和begin进行位置交换，此时key左边的数都比key小，右边的数都比key大。
然后数组被分为成[left,key-1],key,[key+1,right]。此时就可以对这两个区间进行递归。
2.前后指针法
int test2(int* a, int left, int right)
{
int key = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur)
{
swap(&a[prev], &a[cur]);
}
cur++;
}
swap(&a[key], &a[prev]);
return prev;
}前后指针法就是用两个下标来区分出比key要大的数，如果当cur遇到比key要小的数时，且prev++不等于cur时，此时二者之间就发生交换，prev++不等于cur是避免数组同个数据发生交换。
当cur超出right的范围时，表明数组已经遍历完成，此时将key和prev的位置发生互换便完成了排序。
3.非递归法
void qusort2(int* a, int left, int right)
{
ss s1;
ini(&s1);
push(&s1, right);
push(&s1, left);
while (!emp(&s1))
{
int begin = top(&s1);
pop(&s1);
int end = top(&s1);
pop(&s1);
int key = test2(a, begin , end);
if (key + 1 < end)
{
push(&s1, end);
push(&s1, key + 1);
}
if (begin < key - 1)
{
push(&s1, key - 1);
push(&s1, begin);
}
}
del(&s1);
}非递归法用栈来实现，主要是模拟出递归部分，先将数组的左区间和右区间下标压入栈中，然后开始while循环，循环结束的条件是栈为空。
在栈中我们将数组的左区间和右区间的下标取出并删除栈中数据，然后使用前后指针法对整个区域进行排序，此时数组便分为[begin,key-1],key,[ket+1,end]，然后对这两个子区间进行入栈，当区间元素等于1时停止入栈。
在写非递归部分时我们要注意栈的取数据的顺序。
5.归并排序
1.递归算法
void mergetest(int* a, int* tmp,int left, int right)
{
if (left >= right)
{
return;
}
int midi = (left + right ) / 2;
mergetest(a, tmp, left, midi);
mergetest(a, tmp, midi+1, right);
int begin1 = left, end1 = midi;
int begin2 = midi + 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(int) * (right - left + 1));
}
void mergesort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc");
return;
}
mergetest(a, tmp, 0 , n-1);
free(tmp);
tmp = NULL;
}归并排序是将两个或两个以上的有序表合并成一个有序表的过程
在算法的实现中我们先将函数递归分开，分开成长度为2的数组，然后对这个数组进行排序，如果对递归过程不太清楚的话可以画一个递归展开图。
在归并的过程中，我们分为两个区间来归并，[left,midi][midi+1,right]（区间一定用这个范围，不然会造成越界问题），在这两个区间都还没碰到边界的时候对这两个数据进行比较，同时借助第三个数组tmp来完成，将较小的一个数据存放进tmp中。
当有区间已经遍历完成了以后，剩下的两个循环只会运行一个，因为这两个区间已经是有序的，所以只要将还未遍历完成的数据存放进tmp数组中就完成了。
最后用memcpy函数将tmp内已经排完的数据拷贝进原先的a数组中就可以了。
2.归并排序非递归
void mergesort2(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc");
return;
}
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;
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n-1;
}
int j = i;
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 + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap = gap * 2;
}
free(tmp);
tmp = NULL;
}非递归的方法将数组分成gap组排序，每次循环后gap的值翻倍。
在循环的时候容易出现begin2,end2出现越界的情况，如果begin2的位置超出了数组的长度，说明没有第二个子序列需要合并，直接跳出循环，如果只有end2超出数组的长度的话那就将end2修正为正确的值。
使用memcpy将tmp数组中已排序的部分复制回原数组a中
6.非比较排序（基数排序）
void countsort(int* a, int n)
{
int i = 0;
int 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*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("malloc count");
return;
}
for (i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int j = 0;
for (i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i+min;
}
}
free(count);
count = NULL;
} 计数排序是通过新建一个数组，对原数组的数据进行计数，最后在重新排序的算法
在计数排序中，我们首先要算出数组的最大值和最小值，然后算出数组的range，range用来构建新的数组，避免了数组的范围不够。
count[a[i] - min]++ 的作用是将元素 a[i] 的出现次数记录在 count 数组中。每次遇到 a[i]，就将对应的 count 索引的值加一。通过将原数组元素值转换为非负索引，确保可以在 count 数组中安全地记录每个元素的出现次数。
最后进行排序，与统计次数时相反，用a[j++]=i+min来排序。然后free新创建的数组就完成了
标签：begin,初阶,end,int,C语言,gap,排序,数据结构,left From： https://blog.csdn.net/hyxdg/article/details/140309880