时间复杂度：
冒泡排序（n²），选择排序(n²)，插入排序(n ~ n²)，归并排序(nlbn)，快速排序(nlbn ~ n²)
下面都是将已定数组{28,25,20,40,16,30,18,46,41}升序排列：
冒泡排序（n²）：
#include <stdio.h>#include <stdlib.h>#define n 9int main(){int a[n] = {28,25,20,40,16,30,18,46,41};//ÉýÐòint i,j;int tmp;for(i = 0; i < n - 1; i++) {for(j = i + 1; j < n; j++) {if(a[i] > a[j]) {tmp = a[j];a[j] = a[i];a[i] = tmp;}}}for(i = 0; i < n; i++) {printf("%3d",a[i]);}return 0;}
选择排序(n²)：
#include <stdio.h>#include <stdlib.h>#define n 9int main(){int a[n] = {28,25,20,40,16,30,18,46,41};//ÉýÐòint i,j;int min;int tmp;for(i = 0; i < n - 1; i++) {min = i;for(j = i + 1; j < n; j++) {if(a[j] < a[i]) {min = j;}}tmp = a[min];a[min] = a[i];a[i] = tmp;}for(i = 0; i < n; i++) {printf("%3d",a[i]);}return 0;}
插入排序(n ~ n²)
#include <stdio.h>#include <stdlib.h>#define n 9int main(){int a[n] = {28,25,20,40,16,30,18,46,41};//ÉýÐòint i,j;int insert;for(i = 1; i < n; i++) {insert = a[i];j = i - 1;while(j >= 0 && a[j] > insert) {a[j+1] = a[j];j--;}a[j+1] = insert;}for(i = 0; i < n; i++) {printf("%3d",a[i]);}return 0;}
归并排序(nlbn)：
#include <stdio.h>#include <stdlib.h>#define N 9//升序排序void _sort(int a[], int left, int right, int aNew[]);//归并void _merge(int a[],int left, int mid, int right,int aNew[]);int main(){int aNew[] = {0};//用来储存新数组(可以省略返回值)int a[N] = {28,25,20,40,16,30,18,46,41};int i;int left,right;left = 0;right = N - 1;_sort(a,left,right,aNew);for(i = 0; i < N; i++) {printf("%3d",a[i]);}return 0;}//_sortvoid _sort(int a[], int left, int right, int aNew[]) {//anew是辅助数组用来储存新的数组，避免原数组中元素被覆盖//左右边界相等直接返回if(left == right) {return ;}// 2/n前和 2/n后进行排序else {int mid;mid = (left + right) / 2;_sort(a,left,mid,aNew);_sort(a,mid+1,right,aNew);_merge(a,left,mid,right,aNew);//将aNew的值拷贝给aint i;for(i = left; i <= right; i++) {a[i] = aNew[i];}}}//_mergevoid _merge(int a[],int left, int mid, int right,int aNew[]) {int i,j,k;i = left;//左边起始位置j = mid + 1;//右边起始位置k = i;//新数组起始位置while(i <= mid && j <= right) {//左边第一个元素小于右边第一个元素按顺序将左右两个数组储存在aNew里if(a[i] <= a[j]) {aNew[k++] = a[i++];}//大于储存右边数组else {aNew[k++] = a[j++];}}//大于情况处理剩余左边数组while(i <= mid) {aNew[k++] = a[i++];}//奇数情况处理剩余右边数组(只可能剩一位数)if(j <= right) {aNew[k++] = a[j++];}}
快速排序(nlbn ~ n²)：
#include <stdio.h>#include <stdlib.h>#define N 9//快速排序void _quickSort(int a[], int start, int end);//快速查找轴心int _quickPass(int a[],int start,int end);int main(){int a[N] = {28,25,20,40,16,30,18,46,41};_quickSort(a,0,N-1);int i;for(i = 0; i < N; i++) {printf("%3d",a[i]);}return 0;}//_quickSortvoid _quickSort(int a[], int start, int end) {//=????if(start >= end) {return;}else {int tmp;tmp = _quickPass(a,start,end);_quickSort(a,start,tmp-1);-1????_quickSort(a,tmp+1,end);}}//_quickPassint _quickPass(int a[],int start,int end) {//第一次从左边首元素开始int tmp = a[start];//轴心元素int i,j;i = start;j = end;//后面依次左右来回查找while(i < j) {//查找轴心右侧while(j > i) {//从右往左,查找到小于轴心元素的值则交换if(tmp > a[j]) {a[i] = a[j];a[j] = tmp;i++;break;}j--;if(i == j) {break;}}//查找轴心左侧while(i < j) {//从左往右，查找到大于轴心元素的值则交换if(a[i] > tmp) {a[j] = a[i];a[i] = tmp;j--;break;}i++;if(i == j) {break;}}}return i;}
