1. 快速排序
不稳定的排序。
平均(与最好情况)时间复杂度:O(nlgn) | 最坏情况时间复杂度(元素有序,递归栈为 O(n)):O(n2)
适合的数据结构:数组,双向链表。
#include <stdio.h> #include <stdlib.h> int partition(int data[], int low, int high) { int value = data[low]; // can be done randomly while(low < high) { while(low < high && data[high] >= value) --high; data[low] = data[high]; while(low < high && data[low] <= value) ++low; data[high] = data[low]; } data[low] = value; return low; } void QuickSort(int data[], int low, int high) { if(low < high) { int mid = partition(data, low, high); QuickSort(data, low, mid); QuickSort(data, mid+1, high); } } void init(int data[], int length) { for(int i = 0; i < length; ++i) data[i] = rand() % 10000; } int main() { enum{ N = 5000}; int numbers[N] = {0}; init(numbers, N); // if commented out, the numbers is ordered, the stack is N, then overflow! QuickSort(numbers, 0, N-1); for(int i = 0; i < N; ++i) printf("%d\t", numbers[i]); printf("\n"); return 0; }
2. 希尔排序
直接插入排序的改进,是稳定的排序。
Shell’s Sort 又称“缩小增量排序”。
增量序列必须满足:没有除 1 之外的公因子,最后增量值等于 1 。
增量的取法:
dlta[ k ] = 2t-k+1 - 1 时,时间复杂度为 O(n3/2),其中 t 为排序趟数,1 ≤ k ≤ t ≤ floor(log2(n+1))。
dlta[ k ] = 2t-k + 1,0 ≤ k ≤ t ≤ floor(log2(n-1))。1, 2, 3, 5, 9…
dlta[ k ] = 1/2(3t-k - 1),0 ≤ k ≤ t ≤ floor(log3(2n+1))。1, 4, 13, 40…
适合的数据结构: 数组, 双向链表。
#include <stdio.h> #include <stdlib.h> void ShellInsert(int data[], int length, int dk) { int temp, j; for(int i = dk; i < length; ++i) { temp = data[i]; for(j = i-dk; j >= 0 && data[j] > temp; j -= dk) data[j+dk] = data[j]; data[j+dk ]= temp; } } void ShellSort(int data[], int length, int dlta[],int t) /* t 为排序趟数 and dlta 长度 */ { for(int k = 0; k < t; ++k) ShellInsert(data, length, dlta[k]); } void init(int data[], int length) { for(int i = 0; i < length; ++i) data[i] = rand(); } int main() { enum{ N = 100000}; int dlta[] = {7, 3, 1}; int numbers[N] = {0}; init(numbers, N); ShellSort(numbers, N, dlta, 3); /* 3 为a排序趟数 and dlta 长度 */ for(int i = 0; i < N; ++i) printf("%d\t", numbers[i]); printf("\n"); return 0; }
3. 直接插入排序
稳定的排序。
时间复杂度 O(n2)。
适合的数据结构: 数组,双向链表。
void InsertSort(int data[], int length) { int j; for(int i = 1; i < length; ++i) { if(data[i] < data[i-1]) { int value = data[i]; data[i] = data[i-1]; for(j = i-2; j >= 0 && data[j] > value; --j) data[j+1] = data[j]; data[j+1] = temp; } } }
快速排序 && 希尔排序 && 插入排序,布布扣,bubuko.com
原文:http://www.cnblogs.com/liyangguang1988/p/3704715.html