常见的排序算法
排序算法按实现方式，大致分类4大类:
一.交换排序
1
2
1.冒泡排序
2.快速排序
二.插入排序
1
2
1.直接插入排序
2.希尔(shell)排序
三.选择排序
1
2
1.直接选择排序
2.堆(Heap)排序
四.归并排序
交换排序
交换排序的基本思想都为通过比较两个数的大小，当满足某些条件时对它进行交换从而达到排序的目的。
常见的有冒泡排序和快速排序
冒泡排序
基本思想：比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void popSort(int *array, int len)
{
for(int i = 0; i < len; i++)
{
for(int j = 0; j < len - i - 1; j++)
{
if(array[j] > array[j + 1])
{
// swap
array[j] ^= array[j + 1];
array[j + 1] ^= array[j];
array[j] ^= array[j + 1];
}
}
}
}
快速排序
基本思想:选取一个基准元素，通常为数组最后一个元素（或者第一个元素）。从前向后遍历数组，当遇到小于基准元素的元素时，把它和左边第一个大于基准元素的元素进行交换。在利用分治策略从已经分好的两组中分别进行以上步骤，直到排序完成。下图表示了这个过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void quickSort(int * a, int left, int right) {
if (left > right) {
return;
}
int low, high, t, key;
key = a[left];// 基准数
low = left;
high = right;
while (low != high) {
// 从右往左遍历，遇到小于基准数的时候停下，此时的high对应的数字小于基准数
while (a[high] >= key && low < high) {
high--;
}
// 从左往右遍历，遇到大于基准数的时候停下，此时的low对应的数字大于基准数
while (a[low] <= key && low < high) {
low++;
}
// 将low和high位置的数字对调，实现: 小于基准数的都在左边，大于基准数的都在右边
if (low < high) {
t = a[low];
a[low] = a[high];
a[high] = t;
}
}
a[left] = a[low];
a[low] = key;
// 本轮交换结束，获取到了基准数的索引，由此索引将数组拆分成左右2个进行分治递归
quickSort3(a, left, low-1);
quickSort3(a, low + 1, right);
}
插入排序
直接插入排
希尔(shell)排序
选择排序
直接选择排序
堆(Heap)排序
归并排序
基本思想：归并算法应用到分治策略，简单说就是把一个答问题分解成易于解决的小问题后一个个解决，最后在把小问题的一步步合并成总问题的解。这里的排序应用递归来把数组分解成一个个小数组，直到小数组的数位有序，在把有序的小数组两两合并而成有序的大数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <limits.h>
// 合并两个已排好序的数组
void Merge(int a[], int left, int mid, int right)
{
int len = right - left + 1; // 数组的长度
int *temp = new int[len]; // 分配个临时数组
int k = 0;
int i = left; // 前一数组的起始元素
int j = mid + 1; // 后一数组的起始元素
while (i <= mid && j <= right)
{
// 选择较小的存入临时数组
temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= mid)
{
temp[k++] = a[i++];
}
while (j <= right)
{
temp[k++] = a[j++];
}
for (int k = 0; k < len; k++)
{
a[left++] = temp[k];
}
}
// 递归实现的归并排序
void MergeSort(int a[], int left, int right)
{
if (left == right)
return;
int mid = (left + right) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right);
}
int main() {
int a[] = { 5,1,9,2,8,7,10,3,4,0,6 };
int n = sizeof(a) / sizeof(int);
MergeSort(a, 0, n - 1);
printf("排序好的数组为：");
for (int k = 0; k < n; ++k)
printf("%d ", a[k]);
printf("\n");
return 0;
}
选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectSort(int *array, int len)
{
for(int i = 0; i < len - 1; i++)
{
for(int j = i + 1; j < len; j++)
{
if(array[i] > array[j])
{
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
}
}
}
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(int *array, int n)
{
int i, j, key;
for(i = 1; i < n; i++)
{
key = array[i];
for(j = i; j - 1 >= 0 && key < array[j - 1]; j--)
array[j] = array[j - 1];
array[j] = key;
}
}
希尔排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void shellSort(int *array, int n)
{
int i, j, key;
int gap = n >> 1;
while(gap>=1)
{
for(i = gap; i < n; i++)
{
key = array[i];
for(j = i; j - gap >= 0 && key < array[j-gap]; j = j - gap)
array[j] = array[j-gap];
array[j] = key;
}
gap = gap >> 1;
}
}
桶排序
归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void Merge(int a[], int left, int mid, int right, int* temp)
{
int len = right - left + 1; //数组的长度
int k = 0;
int i = left; // 前一数组的起始元素
int j = mid + 1; // 后一数组的起始元素
while (i <= mid && j <= right)
{
// 选择较小的存入临时数组
temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= mid)
{
temp[k++] = a[i++];
}
while (j <= right)
{
temp[k++] = a[j++];
}
for (int k = 0; k < len; k++)
{
a[left++] = temp[k];
}
}
// 递归实现的归并排序
void MergeSort(int a[], int left, int right)
{
if (left == right)
return;
int mid = (left + right) / 2;
int* temp = new int[right - left + 1];
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right, temp);
delete[]temp;
}
堆排序
基数排序
计数排序
排序算法的稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。
算法的辅助空间
严格地说就是除了源数据外其他所有变量.但一般来说,循环变量好像不算在内.
比如将包含n个数据的数组右循环移一个数,除了循环变量外,肯定要用1个变量来保存数组中最后一个数,最后把这个数放到第一位去.这个变量就是辅助的.
现在的计算机内存都很大,一般都考虑用空间来换时间,空间只要不浪费即可,不用追求最优.
各算法的时间复杂度分析
