#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <malloc.h>#include <memory.h>#include <time.h>void print(int a[], int n){int i = 1;while(i<=n){printf("%d,", a[i]);i++;}printf("\n");return;}//直接插入排序，时间复杂度O(n^2),空间复杂度O(1)，稳定排序//a[0]不参与排序，实际排序空间为a[1]~a[n]void InsertSort(int a[], int n){for(int i=2; i<=n; i++){if(a[i]<a[i-1]){a[0] = a[i];int j = i - 1;//扫描有序空间， while(a[0]<a[j]){a[j+1] = a[j];j--;}a[j+1] = a[0];}}printf("InsertSort : ");print(a, n);return;}//一次Shell排序过程void ShellPass(int a[], int n, int increment){for(int i=increment+1; i<=n; i++){if(a[i]<a[i-increment]){a[0] = a[i];int j=i-increment;while(j>0 && a[0]<a[j]){a[j+increment] = a[j];j -= increment;}a[j+increment] = a[0];}}return;}//Shell排序,时间复杂度依赖于增量序列，应避免互为倍数的增量序列，//目前较好时间复杂度为n^1.25~1.6n^1.25,空间复杂度为O(1)，不稳定排序void ShellSort(int a[], int n){int increment = 20;do{increment = increment/3 + 1;ShellPass(a, n, increment);}while(increment>1);printf("ShellSort : ");print(a, n);return;}//冒泡排序,时间复杂度O(n^2),空间复杂度O(1),稳定排序void BubbleSort(int a[], int n){for(int i=1; i<n; ){int lastExchangePos = n;//记录一次排序中最后一次交换的位置，此位置之前的所有数据都已有序 for(int j=n-1; j>=i; j--){if(a[j+1]<a[j]){a[0] = a[j+1];a[j+1] = a[j];a[j] = a[0];lastExchangePos = j+1;}}i = lastExchangePos;}printf("BubbleSort : ");print(a, n);return;}////快速排序，平均时间复杂度为O(nlgn),空间复杂度为O(lgn)~O(n),快速排序不稳定。//C++中快速排序的实现,void QuickSort(int a[], int low, int high){srand(time(0));a[0] = a[rand()%(high-low+1)+low];//随机选择基准，改善快排的性能int tmp = 0;int i = low, j = high;while(i<=j){while(i<high && a[i]<a[0])i++;while(j>low && a[j]>a[0])j--;if(i<=j){tmp = a[i];a[i] = a[j];a[j] = tmp;i++;j--;}}if(j>low)QuickSort(a, low, j);if(i<high)QuickSort(a, i, high);return;}//快速排序的一次划分int Partition(int a[], int low, int high){srand(time(0));int pos = rand()%(high-low+1)+low;a[0] = a[pos];a[pos] = a[low];while(low<high){while(low<high && a[0]<a[high])high--;if(low<high)a[low++] = a[high];while(low<high && a[0]>a[low])low++;if(low<high)a[high--] = a[low];}a[low] = a[0];return low;}//数据结构中标准的快速排序算法void QSort(int a[], int low, int high){if(low<high){int p = Partition(a, low, high);QSort(a, low, p-1);QSort(a, p+1, high);}return;}//直接选择排序，时间复杂度为O(n^2),空间复杂度为O(1),不稳定排序void SelectSort(int a[], int n){for(int i=1; i<=n; i++){int min = i;for(int j=i+1; j<=n; j++){if(a[j]<a[min])min = j;}if(min!=i){a[0] = a[i];a[i] = a[min];a[min] = a[0];}}printf("SelectSort : ");print(a, n);return;}//调整堆void Heapify(int a[], int s, int to){/*//Heapify方法的递归算法a[0] = a[s];int tmp = 2*s;if(tmp+1<=to && a[tmp]<a[tmp+1])tmp++;if(tmp<=to && a[0]<a[tmp]){a[s] = a[tmp];a[tmp] = a[0];Heapify(a, tmp, to);}*///Heapify方法的递推算法 a[0] = a[s];for(int j=2*s; j<=to; j*=2){if(j+1<=to && a[j]<a[j+1])j++;if(j<=to && a[0]>=a[j])break;a[s] = a[j];// a[j] = a[0]; s = j;}a[s] = a[0];return;}//堆排序,最坏时间复杂度nlgn,空间复杂度为O(1)，不稳定排序，适合大量数据的排序void HeapSort(int a[], int n){for(int j=n/2; j>0; j--)Heapify(a, j, n);for(int j=n; j>1; j--){a[0] = a[j];a[j] = a[1];a[1] = a[0];Heapify(a, 1, j-1);}printf("HeapSort : ");print(a, n);return;}//归并排序的一次合并过程void MergePass(int a[], int low, int mid, int high){int *p = (int*)malloc(sizeof(int)*(high-low+1));assert(p!=NULL);int *pi = p;int i = low, j = mid+1;while(i<=mid && j<=high)*(pi++) = (a[i]<=a[j])? a[i++] : a[j++];while(i<=mid)*(pi++) = a[i++];while(j<=high)*(pi++) = a[j++];pi = p;while(low<=high)a[low++] = *(pi++);free(p);return;}//归并排序，时间复杂度O(nlgn),空间复杂度O(n),稳定排序void MergeSort(int a[], int low, int high){if(low<high){int mid = (low+high)/2;MergeSort(a, low, mid);MergeSort(a, mid+1, high);MergePass(a, low, mid, high);}return;}int main(){//source[0]不参与排序，做为辅助空间使用 int source[] = {0, 10, 8, 30, 55, 6, 0, 99, 87, -5, 32, 66, 54, 33, 21, 32, 96, 121, 70};int n = sizeof(source)/sizeof(source[0])-1;int a[sizeof(source)/sizeof(source[0])];memcpy(a, source, sizeof(source));InsertSort(a, n);memcpy(a, source, sizeof(source));ShellSort(a, n);memcpy(a, source, sizeof(source));BubbleSort(a, n);memcpy(a, source, sizeof(source));QuickSort(a, 1, n);printf("QuickSort : ");print(a, n);memcpy(a, source, sizeof(source));QSort(a, 1, n);printf("QSort : ");print(a, n);memcpy(a, source, sizeof(source));SelectSort(a, n);memcpy(a, source, sizeof(source));HeapSort(a, n);memcpy(a, source, sizeof(source));MergeSort(a, 1, n);printf("MergeSort : ");print(a, n);return 0;}
联系客服
