排序算法实现总结(Java)

冒泡排序

public class Bubble { public void sort(Comparable[] a){ int N = a.length; for(int i=0;i<N;i++){ for(int j=i;j<N;j++){ if(a[i].compareTo(a[j])>0){ exch(a, i, j); } } } } public void sort2(Comparable[] a) //正规冒泡 { int N=a.length; for(int i=0;i<N;i++){ for(int j=N-1;j>0;j--){ if(a[j].compareTo(a[j-1])<0){ exch(a, j, j-1); } } } } public void exch(Comparable[] n,int a,int b){ //交换数组中的元素 Comparable temp = 0; temp = n[a]; n[a] = n[b]; n[b] = temp; } public static void main(String args[]){ Integer[] a = {5,6,9,8,7,4,3,2,1,0}; new Bubble().sort(a); for(Comparable i : a){ System.out.print(i+" "); } } }

插入排序

/** * 插入排序 O(n^2) 稳定 * 将每一张牌插入到已经有序的牌中的适当位置 * @author dong * */ public class Insertion { public void sort(Comparable[] a){ int N = a.length; for(int i=1;i<N;i++){ for(int j=i;j>0 && a[j].compareTo(a[j-1])<0;j--){ //直到 j<j-1 不交换 exch(a, j, j-1); //交换 } } } public void exch(Comparable[] n,int a,int b){ //交换数组中的元素 Comparable temp = 0; temp = n[a]; n[a] = n[b]; n[b] = temp; } }

选择排序

/** * 选择排序 O(n^2) 不稳定 * 从未排序的数列中选出最小(大)的放到排序好的最后面，直到所有都有序 * @author dong * */ public class Selection { public void sort(Comparable[] a){ int N = a.length; for(int i=0;i<N;i++){ int min = i; for(int j=i+1;j<N;j++){ if(a[j].compareTo(a[min])<0) min = j; //j<min } exch(a, i, min); } } public void exch(Comparable[] n,int a,int b){ //交换数组中的元素 Comparable temp = 0; temp = n[a]; n[a] = n[b]; n[b] = temp; } }

希尔排序

/** * 希尔排序 O(n^1.3) 不稳定 * 缩小增量排序 先分成若干子序列(相隔h个元素)，分别直接插入排序 * 一次缩减增量h，再排序，基本有序时，对所有元素进行直接插入排序O(n) * @author dong * */ public class Shell { public void sort(Comparable[] a){ int N = a.length; int h = 1; while(h < N/3) h= 3*h + 1; //1,4,13,40.. while(h>=1){ for(int i=h;i<N;i++){ for(int j=i; j>=h && a[j].compareTo(a[j-h])<0; j = j-h){ //j<j-h exch(a, j, j-h); } } h = h/3; } } public void exch(Comparable[] n,int a,int b){ //交换数组中的元素 Comparable temp = 0; temp = n[a]; n[a] = n[b]; n[b] = temp; } }

快速排序

/** * 快速排序 O(N*logN) 不稳定 * 第一个为基准数 ，通过交换，使得基准数左侧全小于它 右侧全大于它（切分） * 再递归分别算两个子序列 ，直到都有序 * @author dong * 改进：在数组小时切换到插入排序 */ public class Quick { public void sort(Comparable[] a){ sort(a,0,a.length-1); } public void sort(Comparable[] a,int lo,int hi){ if(hi <= lo) return; int mid = partition(a, lo, hi); sort(a,lo,mid-1); sort(a, mid+1, hi); } public int partition(Comparable[] a,int low,int high){ //固定切分 Comparable key = a[low]; while(low<high){ while(key.compareTo(a[high])<0 && high > low){ high--; } a[low] = a[high]; while(key.compareTo(a[low])>0 && high > low){ low++; } a[high] = a[low]; } a[high] = key; return high; } }

归并排序

/** * 归并排序 O(N*logN) 稳定 * 自顶向下 归并 将小的有序数组合并成一个有序数组 效率最高的排序算法 * @author dong * */ public class Merge { public static Comparable[] aux; //中间数组 public void sort(Comparable[] a){ aux = new Comparable[a.length]; sort(a,0,a.length-1); } public void sort(Comparable[] a,int lo,int hi){ //将数组a[lo..hi]排序 if(hi <= lo) return; int mid = lo + (hi - lo)/2; sort(a,lo,mid); sort(a, mid+1,hi); merge(a, lo, mid, hi); } public void merge(Comparable[] a,int lo,int mid,int hi){ //两个有序数组归并 int i = lo,j = mid + 1; for(int k=lo;k<=hi;k++){ aux[k] = a[k]; } for(int k=lo;k<=hi;k++){ if(i>mid) a[k] = aux[j++]; //左半边用尽 取右边元素 else if(j>hi) a[k] = aux[i++]; //右半边用尽 取左边元素 else if(aux[j].compareTo(aux[i])<0) a[k] = aux[j++]; //右小于左 else a[k] = aux[i++]; } } }

堆排序 ##

import java.lang.reflect.Array; /** * 堆排序 * @author dong * */ public class Heap { private int[] array; public Heap(int[] array){ this.array = array; } public void heapSort(){ buildHeap(); System.out.println("建堆..."); display(); System.out.println(); int lastIndex = array.length -1; while(lastIndex>0){ swap(0,lastIndex); //堆顶元素和堆底交换 if(--lastIndex == 0) break; //只有一个元素就不用排序 adjustHeap(0, lastIndex); System.out.println("调整堆..."); display(); System.out.println(); } } public void swap(int firstIndex,int lastIndex){ int temp = 0; temp = array[firstIndex]; array[firstIndex] = array[lastIndex]; array[lastIndex] = temp; } //用数组元素建堆 public void buildHeap(){ int lastIndex = array.length -1; for(int i=(lastIndex-1)/2;i>=0;i--){ //最后一个元素的根节点下标 adjustHeap(i, lastIndex); } } //调整rootIndex下标的根节点的子树 public void adjustHeap(int rootIndex,int lastIndex){ //左子结点下标 [2n] 右[2n+1] int biggerIndex = rootIndex; int leftChildIndex = rootIndex*2 + 1; //？+1 int rightChildIndex = rootIndex*2 + 2; if (rightChildIndex<=lastIndex) { if (array[rootIndex]<array[leftChildIndex]||array[rootIndex]<array[rightChildIndex]) {//子节点有比根节点大的 biggerIndex = array[rightChildIndex]>array[leftChildIndex]?rightChildIndex:leftChildIndex; } }else if(leftChildIndex<=lastIndex){ //只存在左子结点 if(array[rootIndex]<array[leftChildIndex]) biggerIndex = leftChildIndex; } if(biggerIndex!=rootIndex){ swap(rootIndex, biggerIndex); adjustHeap(biggerIndex, lastIndex); } } public void printTree(int len){ } public void display(){ for(int i:array){ System.out.print(i + " "); } } public static void main(String[] args) { int[] i ={7,5,1,3,4,9,2,6,8}; Heap heap = new Heap(i); heap.heapSort(); heap.display(); } }