各种排序：
我这里是统一排成升序
各个排序的时间复杂度：
冒泡排序：O(N ^ 2)(适应性不好(即很难在中途完成排序))
插入排序：O(N ^ 2)(在该数组接近有序时，时间复杂度很小)(适应性好(即容易在中途完成排序))
选择排序：O(N ^ 2)
希尔排序：O(N ^ 1.3)(比O(N * logN)大一点)
堆排序：O(N * logN)
快速排序：O(N * logN)
(实际上是O(N ^ 2)，但由于他有很强的适应性，所以一般称他的时间复杂度为O(N * logN))
归并排序：O(N * logN)
计数排序：O(N + count)
冒泡排序：
void Bubble_Sort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}插入排序：
void Insert_Sort(int* a, int n)
{
int i = 1;
while (i < n)
{
if (a[i] > a[i - 1])
{
i++;
continue;
}
int p = i;
int tem = a[i];
while (p >= 1)
{
if (a[p - 1] > tem)
{
a[p] = a[p - 1];
}
else
{
break;
}
p--;
}
a[p] = tem;
}
}希尔排序：
void Shell_Sort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int j = 0; j < n / gap; j++)
{
int i = j + gap;
while (i < n)
{
if (a[i] > a[i - gap])
{
i += gap;
continue;
}
int p = i;
int tem = a[i];
while (p >= j + gap)
{
if (a[p - gap] > tem)
{
a[p] = a[p - gap];
}
else
{
break;
}
p -= gap;
}
a[p] = tem;
}
}
}
}选择排序：
void Select_sort(int* a, int n)
{
int left = 0, right = n - 1;
int begin = 0, end = n - 1;
while (begin < end)
{
left = begin;
right = end;
int min = begin;
int max = end;
while (left <= right)
{
if (a[min] > a[left])
{
min = left;
}
if (a[max] < a[left])
{
max = left;
}
++left;
}
Swap(&a[end], &a[max]);
if (min == end)
{
min = max;
}
Swap(&a[begin], &a[min]);
begin++;
--end;
}
}快速排序：
void Quick_sort(int* a, int begin, int end)
{
assert(a);
if (begin >= end)
{
return;
}
int key = a[begin];
int left = begin;
int right = end;
int keyi = begin;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[keyi] = a[right];
keyi = right;
while (left < right && a[left] <= key)
{
left++;
}
a[keyi] = a[left];
keyi = left;
}
keyi = left;
a[keyi] = key;
Quick_sort(a, begin, keyi - 1);
Quick_sort(a, keyi + 1, end);
} 优化后的快速排序：
用了三数取中(为了应对类似于本身数组就已经有序了的这种极端情况)
以及小区间优化，在数组长度小于10的时候，直接用插入排序减少递归次数
int Get_Middle(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[end])
{
if (a[mid] > a[end])
{
return end;
}
else if (a[mid] > a[begin])
{
return mid;
}
else
{
return begin;
}
}
else if (a[begin] >= a[end])
{
if (a[begin] < a[mid])
{
return begin;
}
else if (a[mid] > a[end])
{
return mid;
}
else
{
return end;
}
}
return -1;
}
void Quick_sort_Opti(int* a, int begin, int end)
{
if (end - begin + 1 <= 10)
{
Shell_Sort(a + begin, end - begin + 1);
return;
}
if (begin >= end)
{
return;
}
int ret = Get_Middle(a, begin, end);
Swap(&a[ret], &a[begin]);
assert(a);
int key = a[begin];
int left = begin;
int right = end;
int keyi = begin;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[keyi] = a[right];
keyi = right;
while (left < right && a[left] <= key)
{
left++;
}
a[keyi] = a[left];
keyi = left;
}
keyi = left;
a[keyi] = key;
Quick_sort_Opti(a, begin, keyi - 1);
Quick_sort_Opti(a, keyi + 1, end);
}下边是用前后指针法写快排，更简单
它也可以用三数取中，随机数取中，小区间优化来提高该效率
void Quick_Loop(int* a, int begin, int end)
{
assert(a);
if (begin >= end)
{
return;
}
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi])
{
Swap(&a[cur], &a[++prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
Quick_Loop(a, begin, keyi - 1);
Quick_Loop(a, keyi + 1, end);
}下边是用非递归的方法实现快速排序：
就是用两个栈存储数组的下标
void Quick_Sort_NonR(int* a, int n)
{
ST st;
STInit(&st);
STPush(&st, n - 1);
STPush(&st, 0);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
if (begin >= end)
{
continue;
}
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi])
{
Swap(&a[cur], &a[++prev]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
STPush(&st, end);
STPush(&st, keyi + 1);
STPush(&st, keyi - 1);
STPush(&st, begin);
}
STDestroy(&st);
}堆排序：
void Down_Adjust(int* a, int parent, int n/*元素的个数*/)
{
assert(a);
assert(n);
while (parent * 2 + 1 < n)
{
int kidi = parent * 2 + 1;
if (kidi + 1 < n && a[kidi + 1] > a[kidi])
{
kidi++;
}
if (a[parent] >= a[kidi])
{
break;
}
else
{
Swap(&a[parent], &a[kidi]);
parent = kidi;
}
}
}
void Down_Adjust_Build(int* a, int n/*元素的个数*/)
{
assert(a);
assert(n);
int parent = (n - 1 - 1) / 2;
while (parent >= 0)
{
Down_Adjust(a, parent, n);
parent--;
}
}
void Heap_Sort(int* a, int n)
{
assert(a);
assert(n);
Down_Adjust_Build(a, 10);
while (n >= 1)
{
Swap(&a[0], &a[n - 1]);
n--;
if (n == 0)
{
break;
}
Down_Adjust(a, 0, n);
}
}归并排序：
递归形式：
void Arrange_Ordered_arr(int* a1, int n1, int* a2, int n2, int* tem)
{
assert(n1);
assert(n2);
assert(a1);
assert(a2);
assert(tem);
int i1 = 0, i2 = 0, i = 0;
while (i1 < n1 && i2 < n2)
{
if (a1[i1] < a2[i2])
{
tem[i++] = a1[i1++];
}
else
{
tem[i++] = a2[i2++];
}
}
while (i1 < n1)
{
tem[i++] = a1[i1++];
}
while (i2 < n2)
{
tem[i++] = a2[i2++];
}
int j = n2 + n1;
int l = 0;
while (j--)
{
a1[l] = tem[l];
l++;
}
}
void Merge_Sort_In_Func(int* a, int* tem, int begin, int end)
{
if (begin == end)
{
return;
}
int mid = (end - begin) / 2 + begin;
Merge_Sort_In_Func(a, tem, begin, mid);
Merge_Sort_In_Func(a, tem, mid + 1, end);
Arrange_Ordered_arr(a + begin, mid - begin + 1, a + mid + 1, end - (mid + 1) + 1, tem + begin);
}
void Merge_Sort(int* a, int n)
{
assert(a);
assert(n);
int* tem = (int*)malloc(sizeof(int) * n);
if (tem == NULL)
{
perror("malloc");
return;
}
Merge_Sort_In_Func(a, tem, 0, n - 1);
free(tem);
tem = NULL;
}非递归形式：
void Merge_SortNonR(int* a, int n)
{
assert(a);
assert(n);
int* tem = (int*)malloc(sizeof(int) * 4);
if (tem == NULL)
{
perror("malloc");
return;
}
int i = 2;
while (i <= n * 2)
{
for (int j = 0; j < n; j += i)
{
int mid = i / 2 + j;//mid是右边数组的初始元素下标
if (mid - 1 >= n)
{
break;
}
int end = j + i - 1;
int count = i / 2;
while (end >= n)
{
end--;
count--;
}
if (count == 0)
{
break;
}
Arrange_Ordered_arr(a + j, i / 2, a + mid, count, tem + j);
}
i *= 2;
}
free(tem);
tem = NULL;
}计数排序：
void Count_Sort(int* a, int n, int min, int max)
{
assert(a);
assert(n);
int arr_n = max - min + 1;
int* tem = (int*)calloc(arr_n, sizeof(int));
if (tem == NULL)
{
perror("calloc");
return;
}
for (int i = 0; i < n; i++)
{
tem[a[i] - min]++;
}
int j = 0;
for (int i = 0; i < arr_n; i++)
{
while (tem[i])
{
a[j++] = i + min;
tem[i]--;
}
}
}各个排序的空间复杂度和稳定性：
空间复杂度：
空间复杂度为O(1)的排序：
插入排序
希尔排序
选择排序
堆排序
冒泡排序
空间复杂度为O(N)的排序：
归并排序
空间复杂度为O(logN)的排序：
快速排序
稳定性：
稳定性好即排列前后数组里边的大小相等的元素的相对位置没有改变
稳定性好的排序：
插入排序
冒泡排序
归并排序
稳定性差的排序：
希尔排序
选择排序
堆排序
快速排序