8种排序其中的五种

时间久了就忘了，把以前的代码拿出来整理一下 插入排序— 直接插入排序(Straight Insertion Sort)

结构图

public class InsertSort { public static void main(String[] args) { int a[] = {3,1,5,7,2,4,9,6,10,8}; InsertSort obj=new InsertSort(); System.out.println("初始值："); obj.print(a); obj.insertSort(a); System.out.println("\n排序后："); obj.print(a); } public void print(int a[]){ for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } public void insertSort(int[] a) { for(int i=1;i<a.length;i++){//从头部第一个当做已经排好序的，把后面的一个一个的插到已经排好的列表中去。 if(a[i]<a[i-1]){ int j; int x=a[i];//x为待插入元素 a[i]=a[i-1]; for(j=i-1; j>=0 && x<a[j];j--){//通过循环，逐个后移一位找到要插入的位置。 a[j+1]=a[j]; } a[j+1]=x;//插入 } } } }

时间复杂度：O（n^2）

希尔排序（Shell`s Sort） . 基本思想

public static void main(String[] args) { int a[] = {3,1,5,7,2,4,9,6,10,8}; ShellSort obj=new ShellSort(); System.out.println("初始值："); obj.print(a); obj.shellSort(a); System.out.println("\n排序后："); obj.print(a); } private void shellSort(int[] a) { int dk = a.length/2; while( dk >= 1 ){ ShellInsertSort(a, dk); dk = dk/2; } } private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了 for(int i=dk;i<a.length;i++){ if(a[i]<a[i-dk]){ int j; int x=a[i];//x为待插入元素 //a[i]=a[i-dk]; for(j=i-dk; j>=0 && x<a[j];j=j-dk){//通过循环，逐个后移一位找到要插入的位置。 a[j+dk]=a[j]; } a[j+dk]=x;//插入 } } } public void print(int a[]){ for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } }

简单选择排序

public static void main(String[] args) { int a[] = {3,1,5,7,2,4,9,6,10,8}; SimpleSelectSort obj=new SimpleSelectSort(); System.out.println("初始值："); obj.print(a); obj.selectSort(a); System.out.println("\n排序后："); obj.print(a); } private void selectSort(int[] a) { for(int i=0;i<a.length;i++){ int k=i;//k存放最小值下标。每次循环最小值下标+1 for(int j=i+1;j<a.length;j++){//找到最小值下标 if(a[k]>a[j]) k=j; } swap(a,k,i);//把最小值放到它该放的位置上 } } public void print(int a[]){ for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } public void swap(int[] data, int i, int j) { if (i == j) { return; } //在不创建对象的基础上 data[i] = data[i] + data[j]; data[j] = data[i] - data[j]; data[i] = data[i] - data[j];`这里写代码片` }

时间复杂度： O(N2) 冒泡排序

private static int a[] = {9,8,7,6,5,4,3,1,2}; public static void main(String args[]){

int m; for(int i = 0; i<a.length;i++){ for(int j = 0;j<a.length-i-1;j++){ if(a[j]>a[j+1]){ m = a[j+1]; a[j+1] = a[j]; a[j] = m; } } } for (int i= 0;i<a.length;i++){ System.out.print(a[i]+"\t"); }

} 时间复杂度 O(N2)

快速排序

int a[] = { 4,5,6,5,4,8,9,4}; //快速排序no1 private static void sortKuaiPaiStep1(int l , int r){ if(r >= r){ return; } int index = sortKuaiPaiStep2(l, r); sortKuaiPaiStep1(l , index - 1); sortKuaiPaiStep1(index + 1 , r); } //快速排序no2 private static int sortKuaiPaiStep2(int l , int r){ if(l < r){ int x = a[l]; while(l < r && x>= a[r]){ r--; } if(l < r){ a[l] = a[r]; l++; } while(l < r && x < a[l]){ l++; } if(l < r){ a[r] = a[l]; r--; } a[l] = x; return l; } return l; }

时间复杂度 最好 O(N*log2N)

平均 O(N*log2N)

最坏 O(N2) 还有三种排序没有会 堆排序 归并排序 基数排序