给出含有n个元素的数组array[n],对其进行排序(排列成从小到大)。
对于每一个算法,需要给出 代码、算法复杂度、空间复杂度、是否稳定。
1.插入排序
void insert_sort(int *array, int n){
for(int j=1;j int i=j-1;
int key=a[j];
while(i>=0 && a[i]>key){
a[i+1]=a[i];
i--;
}
a[i+1]=key;
}
}
复杂度、稳定性 自己从代码看吧
空间复杂度为O(1),因为程序只需要额外的几个变量就可以了。
2.归并排序
void merge(int *A, int p, int q, int r){
int n1=q-p+1;
int n2=r-q;
int *array1 = (int *)malloc( n1*sizeof(int));
int *array2 = (int *)malloc( n2*sizeof(int));
for(int i=0;i array1[i] = A[p+i];
for(int i=0;i array2[i] = A[q+i+1];
int i=0,j=0;
for(int k=p;k<=r;k++){
if( iarray2[j]){
A[k] = array1[i];
i++;
}else if( j A[k] = array2[j];
j++;
}
}
}
void merge_sort(int *array, int p, int r){
if(p q=(p+r)/2;
merge_sort(array, p, q);
merge_sort(array, q+1, r);
merge(array, p, q, r);
}
}
排序的时候只需调用merge_sort(array, 0, n-1)即可。
使用了递归,看起来很复杂,不过算法时间复杂度降为O(nlgn), 稳定倒还是稳定的.
同时时间复杂度增加,需要空间为O(n)。
在本程序中每次调用merge都重新申请,对效率会有影响,改为程序全局申请一个长度为n数组会更好些。
3.堆排序
引入了二叉堆这个数据结构,二叉堆跟完全二叉树很像。
int heap_size; //全局变量
void max_heapify(int *array, int i){
int left = 2*i +1;
int right = 2*i +2;
int largest;
if(left < heap_size && array[left] > array[i])
largest = left;
else
largest = i;
if(right < heap_size && array[right] > array[largest])
largest = right;
if(largest != i){
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
max_heapify(array,largest);
}
}
void build_max_heap(int *array, int n){ //要把数据从小到大排序,就要构建大顶堆,
heap_size = n;
for(int i=n/2; i>=0; i--)
max_heapify(array, i);
}
void heap_sort(int *array, int n){
build_max_heap(array, n);
for(int i=n-1; i>0; i--){
int temp = array[i];
array[i] = array[0];
array[0] = temp;
heap_size--;
max_heapify(array, 0);
}
}
堆排序中,max_heapify时间复杂度O(lgn), build_max_heap时间复杂度O(n),
heap_sort时间复杂度为O(nlogn).
空间复杂度:不需要额外的数组,故空间复杂度为O(1)。
稳定性:不稳定。原因呢?两个相等的元素A、B,原来的时候A在B前面,可在max_heapify过程中比较largest时,A在自己的分支中较小而没有动,B在自己分支中较大就上去了,这时B就排在A前面了。
顺便说一句,堆排序虽然性能不错,但还是比不上下面要讲的快排,但这里讲的堆结构还是有很多应用的,比如用于实现优先队列。max priority queue 和 min priority queue。
4.快速排序
快排在最坏情况下时间复杂度为O(n^2),平均时间复杂度为O(nlgn), 但实际应用中,该算法往往效率很高。
void quick_sort(int *array, int p, int r){
if(p int q = partition(array, p, r);
quick_sort(array, p, q-1);
quick_sort(array, q+1, r);
}
}
int partition(int *array, int p, int r){
int x = array[r];
int i = p-1;
for(int j=p; j if(array[j] <= x){
i++;
int temp= a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = array[i+1];
array[i+1] = x;
array[r] = temp;
return (i+1);
}
空间复杂度:需要程序员搞定的空间还是常数O(1). 但是由于使用了递归,递归栈上会使用一些空间,递归栈上的空间复杂度 最坏O(n),平均O(lgn)。 快速排序是不稳定的。
以下为线性时间排序,这些排序都对数据有一定的限制,因为只要是使用比较来进行排序的算法,都不可能打破O(nlgn)的下限。
5.counting sort 计数排序
计数排序要求输入的含有n个元素的数组中,每个元素的大小都在0~k之间,而且k=O(n)。
void count_sort(int *array, int n, int k){
int *B = (int *)malloc(n*sizeof(int));
int *C = (int *)malloc( (k+1)*sizeof(int));
for(int i=0; i<=k; i++)
C[i] = 0;
for(int i=0; i C[array[i]]++;
for(int i=1; i<=k; i++)
C[i] = C[i] + C[i-1];
for(int i=n-1; i>=0; i--){
B[ C[A[i]] - 1 ] = A[i];
C[A[i]]--;
}
}
这个计数排序需要O(n+k)的额外空间,并且它是稳定的。
若是不要求稳定性,我们可以改写上述算法,改为原地排序,即不需要上面程序中的B数组了。
6.radix sort 基数排序
卡片排序机使用的就是基数排序。基数排序一般用于含有多个域的数据排序。比如一个日期含有年、月、日三个域,对日期进行排序。
radix sort要调用其他的一个稳定排序算法。
void radix_sort(int *array, int d) { //d表示的是数据所划分的域的个数
for(int i=0; i use a stable sort to sort arrya on digit i。
}
给出一个有n个元素的数组,数组中全是d位的数,每个数的每一位都可用k个可能的值(对于十进制整数就是0-9),针对d位中每一位的排序使用计数排序,那么基数排序的时间复杂度为O(d(n+k))。
7.bucket sort 桶排序
还有一些排序方法 在算法导论中没有提到:
冒泡排序 O(n^2),稳定
希尔排序 O(n^2) 不稳定
选择排序 O(n^2) 不稳定
阅读(1433) | 评论(0) | 转发(0) |