关于排序

我目前已经学会的排序以及理解(会不断更新)

先贴个交换函数:

1
2
3
4
5
6
void Swap(int A[],int i,int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}

冒泡排序

这是进大学后c语言课本上介绍的第一个排序,也是最简单,最容易理解的一个排序,顾名思义,就像冒泡一样,一次一次把最值往最后面放,完成排序。函数代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(int A[],int n)
{
for(int j = 0;j < n - 1;j++)
{
for(int i = 0;i < n - 1 - j;i++)
{
if(A[i] > A[i + 1]) //从小到大排序
{
Swap(A,i,i + 1);
}
}
}
}

冒泡排序是稳定的,因为即使有相同的数也不会打乱原来是次序,平均时间复杂度:O(n²)。

选择排序

​ 相比于相邻交换的冒牌排序,选择排序是通过从未排序的数据元素中选出最值放在该序列的起始位置,直到所有元素排完,同样需要循环两次,无法优化时间。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelectionSort(int A[],int n)
{
for(int i = 0;i < n - 1;i++)
{
int min = i;
for(int j = i + 1;j < n;j++)
{
if(A[j] < A[min])
{
min = j;
}
}
if(min != i)
{
Swap(A,min,i);
}
}
}

选择排序是不稳定的,因为如果有相同的数的话是可以改变原来次序的,平均时间复杂度:O(n²)。

插入排序

​ 看到这个方法,我的第一反应便是抓扑克牌,原理和抓牌原理一样,即,左手上的牌是已经排好序了的,将左手上的牌依次和抓到的牌比较,如果大于抓到的牌便把这张牌左移,然后插入抓到的牌。函数代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertionSort(int A[],int n)
{
for(int i = 1;i < n;i++)
{
int get = A[i];
int j = i - 1;
while(j >= 0 && A[j] > get)
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = get;
}
}

相同的牌不影响顺序,插入排序是稳定的,平均时间复杂度:O(n²)。

快速排序

​ 快速排序基于一种二分的思想,即以一个数为基准数,不断将数组二分,最终当所有基准数都归位后,排序也就完成了。快速排序之所以较快,是因为每次交换都是跳跃式的。函数代码如下:(千万注意下标是从0开始的 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quicksort(int arr[],int left,int right)
{
if(left > right) return;
int i,j,temp;
temp = arr[left];//temp为基准数
i = left;
j = right;
while(i != j)
{
//基准数在左边,所以要从右边开始找
while(arr[j] >= temp && i < j)j--;
//再从左往右找
while(arr[i] <= temp && i < j)i++;
//如果没有相遇。就交换
if(i < j) Swap(arr,i,j);
}
arr[left] = arr[i];
arr[i] = temp;
quicksort(arr,left,i - 1);//继续处理左边
quicksort(arr,i + 1,right);//继续处理右边
}

归并排序

归并排序的原理是分治法,简单点说就是把一个序列拆成多个子序列,将子序列排好序后,再将其合并为一个序列。归并排序的效率也比较可观,达到了o(NlogN)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void mergeArray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last, k = 0;
while(i <= m && j <= n)
{
if(a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while(i <= m) temp[k++] = a[i++];
while(j <= n) temp[k++] = a[j++];
for(i = 0;i < k;i++) a[first + i] = temp[i];
}
1
2
3
4
5
6
7
8
9
10
void mergeSort(int a[], int first, int last, int temp[])
{
if(first < last)
{
int mid = (first + last) / 2;
mergeSort(a, first, mid, temp);//处理左边
mergeSort(a, mid + 1,last, temp);//处理右边
mergeArray(a, first, mid, last, temp);//合并
}
}

堆排序

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
void max_heapify(int array[], int start, int end){
int dad = start;
int son = dad * 2 + 1;
while(son <= end){//子节点在范围内
if(son + 1 <= end && array[son] < array[son+1]){
son++;
}
if(array[dad] > array[son]){
return;//父亲节点大于子节点说明已经调整完毕
}
else{
swap(array[dad],array[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heapSort(int array[], int len){
for(int i = len/2 - 1;i >= 0;i--){
max_heapify(array, i, len-1);
}
for(int i = len-1;i > 0;i--){
swap(array[0], array[i]);
max_heapify(array, 0, i-1);
}
}