几种简单排序算法总结

冒泡排序

public static void main(String[] args) { int[] a={31,32,4,5,45,65,76,44,65}; output(a); //共排序n-1趟 for(int i=0;i<a.length-1;i++)//i代表趟数 //每一趟从第一个元素到倒数第二个元素 for(int j=0;j<a.length-1-i;j++) { if(a[j]>a[j+1]) //相邻元素比较交换 { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } output(a); }

选择排序

public static void main(String[] args) { int[] a={31,32,4,5,45,65,76,44,65}; output(a); //共排序n-1趟 for(int i=0;i<a.length-1;i++){//i代表趟数 //每一趟排序找出记录中最大的数放在本趟记录的末位 for(int j=0;j<a.length-i-1;j++) { //从第一个元素到倒数大二个元素，每个元素和倒数第一的元素比较并交换 if(a[j]>a[a.length-i-1]) { int temp=a[j]; a[j]=a[a.length-i-1]; a[a.length-i-1]=temp; } } }output(a); }

插入排序

public static void main(String[] args) { int[] a={31,32,4,5,45,65,76,44,65}; output(a); //共排序n-1趟 for(int i=0;i<a.length-1;i++){//i代表趟数 //每一趟排序，将有序表后面的相邻元素插入到有序表中 int key=a[i+1]; for(int j=i;j>=0;j--) { //将大于当前插入元素的其他元素右移 if(a[j]>key) { a[j+1]=a[j]; int temp=a[j]; a[j]=a[a.length-i-1]; a[a.length-i-1]=temp; } } } output(a); }

快速排序

public static void main(String[] args) { int[] a={31,32,4,5,45,65,76,44,65}; output(a); quick(a); output(a); } //快速排序：传入排序数组a public static void quick(int[] a) { qsort(a,0,a.length-1); } //划分方法：对给定数组a的a[low...high]进行划分，完成后返回中轴元素的下标位置 public static int partition(int[] a,int low,int high) { //选出中轴元素 int key=a[low]; //设置首尾指针 int i=low,j=high; //只要首尾指针不重合 while(i<j) { //尾指针不断向左走，直到其指向的元素小于中轴元素 while(a[j]>=key&&i<j) j--; //将此元素放到左边首指针位置处。 a[i]=a[j]; //首指针不断向又走右走，直到其指向的元素大于中轴元素 while(a[i]<key&&i<j) i++; //将此元素放置到右边尾指针位置处 a[j]=a[i]; } //将首尾指针重合后， 将中轴元素放置到此位置 a[i]=key; //返回中轴元素的下标位置 return i; } //快速排序递归方法：给定数组a[low...high]快速排序 public static void qsort(int[] a,int low,int high) { if(low<high) { //先划分 int mid=partition(a,low,high); //对左半部分做划分 qsort(a,low,mid-1); //对右半部分做划分 qsort(a,mid+1,high); } }

算法复杂度比较