常见的排序算法
常见的排序算法如下：
各个排序算法思想与实现：
1.插入排序分为：直接插入排序、选择排序
（1）.直接插入排序
将一个数据插入到一个有序区间中，区间不断扩大，直到数据被插完。
void InsertSort(int* a, int n)
{
assert(a);
int i = 0;
int end = 0;
for (i = 0; i < n-1; i++)//最多是倒数第一个往前面插入，i取值最大是n-2
{
end = i;//end是有序区间下标结尾
int tmp = a[end + 1];
while (n >= 0)//只要下标还在范围内，不符合顺序就调整
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
//不管是n==-1,还是break跳出来，都将tmp放到end+1位置
a[end + 1] = tmp;
}
}（2）希尔排序
是直接插入的优化，通过不断调整间距gap值(从大->小)使得数据整体接近有序，降低时间复杂度但是需要注意的的，并不是单独一组一组排，而是挨着排，只是自己往自己区间里排便可。
void ShellSort(int* a, int n)
{
assert(a);
int gap = n;
int i = 0;
int end = 0;
while (gap > 1)
{
gap = gap / 3 + 1;//保证最后一次一定是1
for (i = 0; i<n - gap; i++)
{
end = i;
int tmp = a[end + gap];
while (n >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}2.选择排序分为：直接选择排序、堆排序
（1）选择排序
每次遍历一遍找出区间内最小的、最大的，然后将它们放在首尾，然后缩小区间继续...
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
assert(a);
int begin = 0;
int end = n - 1;
while (begin < end)//当区间存在，就一直找
{
int max = begin;
int min = begin;
for (int i = begin; i <= end; i++)//找出每个区间内最大值、最小值下标
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
}
//找出来后，将两个数据放在首、尾
Swap(&a[begin], &a[min]);
if (begin == max)//如果最大的值在首部，以上会被换走
{
max = min;
}
Swap(&a[end], &a[max]);
//每安排出一对数据，就缩小区间
begin++;
end--;
}
}（2）堆排序
建堆-交换-首元素向下调整
AdjustDown(int* a, int n, int root)
{
int parent = root;
int child = 2 * parent + 1;
while (child < n)//说明此时parent不是叶子结点，继续调整
{
if (child + 1 < n && a[child + 1] > a[child])//找出大孩子
{
child++;
}
//来到这，a[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)
{
assert(a);
//建堆
int end = n - 1;
int i = 0;
for (i = (end - 1) / 2; i >= 0; i--)
{
//从倒数第一个非叶子结点开始向下调整
AdjustDown(a, n, i);
}
//交换、调整
end = n - 1;
while (end > 0)
{
Swap(&a[0],&a[end]);
AdjustDown(a, end, 0);
end--;
}
}3.交换排序分为：冒泡排序、快速排序
（1）冒泡排序
n个数据需要冒n-1趟，每趟需要比较n-趟数
（2）快速排序
从数据中找一个key将数据划分成左边+key+右边，并且满足：key大于左边的，小于右边的，即将数据key放到它最终要放的位置，然后左边和右边的数据，分别可以用递归思想，继续划分，直到key左右两边都是一个数据说明整体有序。//而这里从数据中找一个key将数据划分成左边+key+右边这个做法有三种（三个版本）：(1)首尾指针交换法 (2)填坑法 (3)前后指针法.
快排有两个优化的点：(1)找key时使用的“三数取中”(避免数据逆序时，选取key值不合适导致效率下降，一般key值选取最左边的数据) (2)小区间优化(避免区间较小使用快排递归的消耗，这些较小的区间通过插入排序直接解决)。
此外，快排也可以使用“栈”进行非递归实现从数据中找一个key将数据划分成左边+key+右边，返回key所在的下标
版本(1):首尾指针交换法
默认key值选最左边的，end从尾开始找，大于key的直接往前走，遇到小于key的停下来，begin从头开始找，小于key的直接往后走,遇到大于key的停下来，将二者停下来后下标所对应的数据交换，重复以上工作，直到二者相遇，将key值与相遇时所对应下标值交换。这时达到了key大于左边的，小于右边的。
需要注意的是：如果key值默认选取最左边的，那么就要end现开始走，这样能够保证最后相遇时下标所对应的值小于key,因为这个值最后要被换到左边，所以一定要满足小于key才行
int PartSort1(int* a, int begin, int end)
{
int key = begin;//key是最左边的下标
while (begin < end)//当二者没有相遇就继续
{
while (begin < end && a[end] >= a[key])
{
--end;
}
while (begin < end && a[begin] <= a[key])
{
++begin;
}
Swap(&a[begin], &a[end]);//交换
}
//交换key值和相遇时那个值
Swap(&a[key], &a[begin]);
return begin;//返回key值所对应的下标
}
void QuicSort(int* a, int left, int right)
{
int div = 0;
if (left >= right)//区间只剩一个值，或者区间不合法
return;
//PartSort()将数据分成：[left, div-1]key[div+1, right]
div = PartSort1(a, left, right);
//两个区间分别子问题进行递归
QuicSort(a, left, div-1);
QuicSort(a, div+1, right);
}版本2：填坑法。
默认也是最左边的是key值，先将其保存在一个临时变量中，那么这个位置就被空出来了，相当于一个“坑”，然后让end从后面开始找找，遇到大于key的直接往前走，遇到小于key的停下来，放在前面这个“坑”中，那个么end空出来的这个也是一个“坑”，然后再让begin从前往后找，遇到小于key的直接往后找，遇到大于key的放在刚刚那个“坑”中，反复重复以上，直到begin和end相遇时，将相遇时下标所对应的数据与key值交换，这就做到了key比左边打，比右边小。
int PartSort2(int* a, int begin, int end)
{
int tmp = a[begin];//先将key值保存在tmp中
while (begin < end)
{
while (begin<end && a[end]>=tmp)
{
--end;
}
a[begin] = a[end];//填坑
while (begin < end && a[begin] <= tmp)
{
++begin;
}
a[end] = a[begin];//填坑
}
a[begin] = tmp;//将key值放在它该放的位置(begin与end相遇时下标)
return begin;
}
void QuicSort(int* a, int left, int right)
{
int div = 0;
if (left >= right)//区间只剩一个值，或者区间不合法
return;
//PartSort()将数据分成：[left, div-1]key[div+1, right]
div = PartSort2(a, left, right);
//两个区间分别子问题进行递归
QuicSort(a, left, div - 1);
QuicSort(a, div + 1, right);
}版本(3):前后指针法
用两个指针，cur从头开始往后找，遇到大于key的，直接往前走，此时prev不动的，遇到小于key的，让prev向前走一下所对应的值与这个小于key的值交换一下，，即prev走过的都是小于key值的，而从prev下一个到vur中间的都是大于key的。
int PartSort3(int* a, int begin, int end)
{
int key = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)//将数据遍历一遍
{
//小于的话，prev往前走，再一交换
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
++cur;//不管大于还是小于,cur总是要移动
}
Swap(&a[key], &a[prev]);
return prev;
}
void QuicSort(int* a, int left, int right)
{
int div = 0;
if (left >= right)//区间只剩一个值，或者区间不合法
return;
//PartSort()将数据分成：[left, div-1]key[div+1, right]
div = PartSort3(a, left, right);
//两个区间分别子问题进行递归
QuicSort(a, left, div - 1);
QuicSort(a, div + 1, right);
}快速排序的优化方案有两种：(1)取key“三数取中法”(2)小区间优化(1):
（1）三数取中法：
之前我们都是默认key值是最左边的，但是当数据有序时，key值选择最左边导致左右区间不均匀，于是我们使用最左边、最右边、中间三个值中中间那个值作为key值。需要注意的是，为了可以复用以上代码，我们将选出来那个数与最左边的数交换，这样使得key值仍然在最左边，可以继续使用上面的代码。
//选取三个数据中中间那个值的下标
int GetMidIndex(int* a, int begin, int end)
{
int mid = begin + (begin - end) >> 1;
//选择begin,mid,end下标所对应元素，大小是中间的那个，返回其下标
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
//来到这说明a[begin]<a[mid],a[mid]>a[end],即a[mid]最大
//那只需比较a[begin]和a[end]即可
else if (a[begin] > a[end])
{
return begin;
}
else
{
return end;
}
}
else//说明a[begin]>a[mid]
{
if (a[mid] > a[end])
{
return mid;
}
//说明a[begin]>a[mid],a[mid]<a[end],即a[mid]最小
//只需要比较a[begin]和a[end]即可
else if (a[begin] > a[end])
{
return end;
}
else
{
return begin;
}
}
}
//当中间值下标找到后，将其值与最左边值交换，使得key值还是在最左边。
//因为我们只是换了一下key值的选取，位置仍然在最左边，这样就可以
//继续使用三个版本的PartSort()函数了
int PartSort1(int* a, int begin, int end)
{
int mid = GetMidIndex(a, begin, end);//获取中间值的下标
Swap(&a[mid], &a[begin]);
int key = begin;//key是最左边的下标
while (begin < end)//当二者没有相遇就继续
{
while (begin < end && a[end] >= a[key])
{
--end;
}
while (begin < end && a[begin] <= a[key])
{
++begin;
}
Swap(&a[begin], &a[end]);//交换
}
//交换key值和相遇时那个值
Swap(&a[key], &a[begin]);
return begin;//返回key值所对应的下标
}
void QuicSort(int* a, int left, int right)
{
int div = 0;
if (left >= right)//区间只剩一个值，或者区间不合法
return;
//PartSort()将数据分成：[left, div-1]key[div+1, right]
div = PartSort1(a, left, right);
//两个区间分别子问题进行递归
QuicSort(a, left, div-1);
QuicSort(a, div+1, right);
}
（2）小区间优化
当区间较大时，我们使用快速排序，由于快排是递归的，因此当递归到较小区间时，还使用递归比较耗时，这时候我们可以直接采用“快速排序”解决小区间的排序，提高效率。
void QuicSort(int* a, int left, int right)
{
int div = 0;
if (left >= right)//区间只剩一个值，或者区间不合法
return;
//当区间一定大时，使用快速排序
if (right - left > 10)
{
//PartSort()将数据分成：[left, div-1]key[div+1, right]
div = PartSort1(a, left, right);
//两个区间分别子问题进行递归
QuicSort(a, left, div - 1);
QuicSort(a, div + 1, right);
}
else//小区间直接插入排序
{
InsertSort(a+left, right-left+1);
}
}快速排序的“非递归”实现：
通过“栈”实现。将区间入栈(先入右，再入左)只要栈不为空，将区间取出来，调用PartSort()函数将该区间数据分成三部分。然后只要被划分的左右两个区间合法，再将其入栈，下一次再取出栈顶元素(区间)继续调用PartSort()进行划分，区间小到一定区间，区间不合法，不入栈，然后栈中区间被处理完，数据就有效了。模拟递归，先处理左区间，再处理右区间。
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top;
int _capacity;
}Stack;
void StackInit(Stack* ps, int n);//初始化，容量为n
void StackDestory(Stack* ps);
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//取栈顶元素
int StackSize(Stack* ps);//取栈中元素个数
int StackEmpty(Stack* ps);//判断栈是否为空
void StackInit(Stack* ps, int n)
{
assert(ps);
ps->_a = (STDataType*)malloc(sizeof(STDataType)*n);
ps->_top = 0;
ps->_capacity = n;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = 0;
ps->_capacity = 0;
}
void StackPush(Stack* ps, STDataType x)//入栈
{
assert(ps);
if (ps->_capacity == ps->_top)//栈满了，增容
{
STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * 2 * sizeof(STDataType));
if (tmp != NULL)
{
ps->_a = tmp;
}
ps->_capacity *= 2;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
void StackPop(Stack* ps)//出栈
{
assert(ps);
if (ps->_top > 0)
{
ps->_top--;
}
}
STDataType StackTop(Stack* ps)//取栈顶元素
{
assert(ps);
return ps->_a[ps->_top - 1];
}
int StackSize(Stack* ps)//取栈中元素个数
{
assert(ps);
return ps->_top;
}
int StackEmpty(Stack* ps)//判断栈是否为空
{
assert(ps);
return ps->_top == 0 ? 0 : 1;//空返回0
}
void QuickSort(int* a, int left, int right)
{
Stack st;
StackInit(&st,10);
//先将两个大的区间入栈
StackPush(&st, right);
StackPush(&st, left);
while (StackEmpty(&st) != 0)
{
int begin = StackTop(&st);//左区间
StackPop(&st);
int end = StackTop(&st);//右区间
StackPop(&st);
//调用PartSort()对从栈中取出来的区间进行
//一次划分
int div = PartSort1(a,begin,end);
//如果区间合法，再次入栈，使得下一次取出来
//再次调用PartSort()进行处理
if (begin < div - 1)
{
StackPush(&st, div-1);
StackPush(&st, begin);
}
if (div + 1 < end)
{
StackPush(&st, end);
StackPush(&st, div+1);
}
}
}4.归并排序
将一组数据二分成左右两部分，左边有序，右边有序，将左右两边合并整体有序。如果左边、右边的没有序就递归到子问题，直到是不可分割的子问题。需要注意的是：左右区间合并的时候是合并到一个临时数组中，然后再拷回原来的数组中。
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)//区间中只有一个值，或者区间不合法
return;
//将数据分成两部分[begin, mid] [mid+1, end]
int mid = begin + ((end - begin) >> 1);
//递归子问题分成不可再分的小区间
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
//合并
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int index = begin;
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++];
}
//将放在临时数组tmp中的归并结果拷回原地方
index = begin;
while (begin <= end)
{
a[index++] = tmp[begin++];
}
}
void MergeSort(int* a, int n)
{
assert(a);
int* tmp = (int*)malloc(sizeof(int)*n);
_MergeSort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}5.非比较排序
也称为“计数排序”，即统计相同元素出现次数，根据统计结果将序列回收到原来序列。
void CountSort(int* a, int n)
{
//计算范围
int max = a[0];
int min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int range = max - min + 1;
//根据范围开辟统计数据出现次数的数组空间
int* count = (int*)malloc(sizeof(int)*range);
memset(count, 0, sizeof(int)*range);
//统计每个数据出现的次数，并且将次数放在相对位置下标处
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//将数据还原
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[j++] = j + min;
}
}
}以下是算法性能分析：