排序算法（1）
1.冒泡排序
冒泡排序（Bubble
Sort）它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。
经典的实现是两层for循环 时间复杂度是O（n**2）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <stdio.h>
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
|
为了优化性能，考虑引入一个flag，当次序正常则不再进行交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <stdio.h>
void bubblesort(int* a,int n)
{
bool flag=true;
while(flag)
{
flag=false;
for(int i=0;i<n-1;i++)
{
if(a[i]>a[i+1]){
flag=true;
int t=a[i];
a[i]=a[i+1];a[i+1]=t;
}
}
}
}
int main()
{
int a[]={1,5,11,6,12,7,14,9,18};
int n= sizeof(a)/sizeof(*a);
bubblesort(a,n);
for(int j=0;j<=n-1;j++) printf("%d ",a[j]);
}
|
2.选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
无论怎样，这个算法的时间复杂度都是O（n**2）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void swap(int*a,int*b)
{
int tem=*a;
*a=*b;
*b=tem;
}
void selectinsort(int*a,int len)
{
for(int i=0;i<=len-1;i++)
{ int min=i;
for(int j=i+1;j<len;j++)
{ if(a[j]<a[min]) min=j;}
swap(&a[i],&a[min]);
}
}
|
3.插入排序
插入排序（英语：Insertion
sort）它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
演示升序排列算法
1
2
3
4
5
6
7
8
9
10
11
12
13
| void insertion_sort(int a[], int len)
{
for(int i=1;i<len;i++)
{
int j=i-1;
while(j>=0&&a[i]<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=a[i];
}
}
|
4.归并排序
归并排序，先拆后并。将整个数组利用函数递归不断二分，直到无法二分为止。然后合并一个个有序数组。
时间复杂度O（nlogn)
私以为归并排序首先要写出归并函数merge.应当指出,实质性的排序过程发生在merge函数里，下面递归时，堆栈过程中只是在不断二分数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void merge(int *a,int left,int mid,int right) //传入int*a是为了方便的使用数组中元素
{
int i=left,j=mid+1,k=0; //i代表左数组起始，j代表右数组起始
int *temp=(int*)malloc((right-left+1)*sizeof(int));
while(i<=mid&&j<=right) //循环直到一个数组变空
{
if(a[i]<a[j])
{
temp[k]=a[i];
k++;i++;
}
else
{
temp[k]=a[j];
k++;j++;
}
}
for(;i<=mid;i++,k++) temp[k]=a[i]; //把剩下的还有数的数组存放进temp之中去
for(;j<=right;j++,k++) temp[k]=a[j];
for(i = 0; i < k; i++) //注意一定要讲temp数组复制到a数组之中去。
a[left++] = temp[i];
}
|
然后进行递归即可。
1
2
3
4
5
6
7
8
9
| void merge_sort(int arr[], int left, int right)
{
if (left < right) { // 如果左边界小于右边界，说明序列中至少有两个元素
int mid = (left + right) / 2; //
merge_sort(arr, left, mid); // 对左半部分的序列递归
merge_sort(arr, mid + 1, right); // 对右半部分的序列递归序
merge(arr, left, mid, right); // 将左右两个有序的子序列合并成一个有序的序列
}
} //可以发现只有merge后函数才能到达出口，因此总可以确保最后最小单元序列merge
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int main()
{
int arr[] = {7, 5, 2, 4, 1, 6, 3, 0}; int len = sizeof(arr) / sizeof(int);
merge_sort(arr, 0, len - 1);
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
|
5.快速排序
快速排序是一种非常巧妙的排序方式，它仍然运用了分治的思想。
快速排序的思路大概是这样的，取数组中任意一个数为基准base（一般取第一个数），通过下述方法使得base左边的数都比它小，base右边的数都比它大。再对左右子序列分而治之。
引入两个索引indexl和indexr。取第一个数为base，从最右向左寻找（insexr–），直到找到比base更小的数，交换base与这个数的位置，此时base右边的数一定都是比base大的数，此时从左向右（indexl++）寻找，以此类推，直到indexr=indexl,排序结束。我一开始的思路是这样的，自己搓出来一个比较臃肿的函数。
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
| void partition(int*a,int p,int q)
{
int temp;
int r=q;
int l=p;
int base=p;
while(1)
{
while(l<r&&a[r]>=a[base])
{
r--;
}
if(l==r) break;
temp=a[base];
a[base]=a[r];
a[r]=temp;
base=r;
while(l<r&&a[l]<=a[base])
{
l++;
}
if(l==r) break;
temp=a[base];
a[base]=a[l];
a[l]=temp;
base=l;
}
}
|
这个函数不太好的地方在于交换确实是具象的交换，而且还要判定两次break；写起来比较麻烦，但是比较容易理解，动态性比较强。还有一种更简明的写法，就是不把base交换来交换去，最后再把base填回来。
从右向左寻找，找到比base小的a[r]之后赋值给a[l],这样a[l]及其左边都比base小，再从左向右找，找到a[l]大于base，a[l]赋值给a[r]······这像一个堆积过程，左边堆积比base小的数，右边堆积比base大的数，当左右相遇，把相遇点赋值为base即可。(此处手模一下l=r
的时候发生了什么，这里重合的时候，重合点是等于上一个索引的元素值的这就是说重合点元素重复了两次，所以接下来要把缺失的base放在这个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void partition(int* a, int p, int q)
{
int temp;
int l = p;
int r = q;
int base = a[p];
while(l < r)
{
while(l < r && a[r] >= base) r--;
a[l] = a[r];
while(l < r && a[l] <= base) l++;
a[r] = a[l];
}
a[l] = base;
}
|
为了方便下面的操作，我们利用partition函数返回最后的l或者r，作为分治时分区的标准。
完整代码如下
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
| #include<stdio.h>
#include<string.h>
#include<stdlib.h>
int partition(int* a, int p, int q)
{
int temp;
int l = p;
int r = q;
int base = a[p];
while(l < r)
{
while(l < r && a[r] >= base) r
a[l] = a[r];
while(l < r && a[l] <= base) l++;
a[r] = a[l];
}
a[l] = base; //or a[r]=base
return l;
}
void quick_sort(int *a,int p,int q)
{
if(p>=q) return;
int mid=partition(a,p,q);
quick_sort(a,p,mid);
quick_sort(a,mid+1,q);
}
int main()
{
int a[10]={2,0,1,3,5,4,6,7,9,8};
quick_sort(a,0,9);
for(int i=0;i<10;i++) printf("%d ",a[i]);
}
|