简单总结下各种排序算法

编程技术  /  houtizong 发布于 3年前   73

public static void bubbleSort(int[] c){for(int i=0,len=c.length;i<len;i++){for(int j=0;j<len-i-1;j++){if(c[j]>c[j+1]){Helper.swap(c, j+1, j);}}}}public static void selectionSort(int[] c){for(int i=0,len=c.length;i<len;i++){int k=i;for(int j=i+1;j<len;j++){if(c[j]<c[k])k=j;}if(k!=i){Helper.swap(c, i, k);}}}public static void insertionSort(int[] a){for(int i=1,len=a.length;i<len;i++){int j=i;while(j>0){if(a[j]<a[j-1]){Helper.swap(a,j,j-1);}j--;}}}public static void quickSort2(int[] c,int begin,int end){//update 2012/7/1if(c==null||c.length<2){return;} if(begin>end)return;  int len = c.length; if(begin<end&&(0<=begin&&begin<len)&&(0<=end&&end<len)){ int point=c[begin];       int i=begin,j=end;       int index=i;       while(i<j){      while(c[j]>=point&&i<j)j--;           if(i<j){               c[index]=c[j];               index=j;           }          while(c[i]<=point&&i<j)i++;           if(i<j){               c[index]=c[i];               index=i;           }       }       c[index]=point;       quickSort2(c,begin,i-1);       quickSort2(c,i+1,end);  }}public static void quickSort(int[] c,int begin,int end){if(begin>end)return;int low=begin;int high=end;boolean flag=true;while(low!=high){if(c[low]>c[high]){Helper.swap(c, low, high);flag=!flag;}if(flag){high--;}else{low++;}}quickSort(c,begin,low-1);quickSort(c,high+1,end);}            /**     * 用最大堆实现“就地”升序排序     * 思路：     * 1.“自下而上”，将整个数组初始化建成一个最大堆     *   从最右下方的子堆——也就是以最后一个非叶子结点为根结点（lastRootindex）的子堆——开始，     *   调整各个子堆使之为最大堆，最后使得整个数组成为一个最大堆     *   注意到从 0, 1, 2, ...lastRootIndex 的结点都是非叶子结点，都作为子堆需要调整     * 2.将当前堆顶元素（最大元素）与堆的最后一个元素交换，这样，当前最大值就排到末尾了     * 3.将堆的大小减1（排除最后一个元素），重新调整使得堆仍为最大堆，直到排序完毕     *   注意这时候的调整是“自上而下”，选举出当前的最大值放至堆顶     */    public static void heapsort(int[] array) {        int lastIndex = array.length - 1;        int lastRootIndex = (lastIndex - 1) / 2;        for (int root = lastRootIndex; root >= 0; root--) {            reheap(array, root, lastIndex);        }        for (int last = lastIndex; last >= 0; last--) {            swap(array, 0, last);            reheap(array, 0, last - 1);     //堆大小减1        }        System.out.println(Arrays.toString(array));    }    /**     * 调整使之仍为最大堆     * @param heap heap是这样一个“半堆”：执行调整操作前是一个最大堆。将最大堆的堆顶元素移除，并替换为最大堆的最后一个元素，成为“半堆”     * @param rootIndex “半堆”的根     * @param lastIndex “半堆”的最后一个元素     */    public static void reheap2(int[] heap, int rootIndex, int lastIndex) {        int orphan = heap[rootIndex];        int leftIndex = rootIndex * 2 + 1;        boolean done = false;        while (!done && leftIndex <= lastIndex) {            int largeIndex = leftIndex;            int rightIndex = leftIndex + 1;            if (rightIndex <= lastIndex && heap[rightIndex] > heap[leftIndex]) {                largeIndex = rightIndex;            }            if (heap[largeIndex] > orphan) {                heap[rootIndex] = heap[largeIndex];                rootIndex = largeIndex;                leftIndex = rootIndex * 2 + 1;            } else {                done = true;            }        }        heap[rootIndex] = orphan;    }public static void mergeSort(int[] c,int low,int high,int[] tmp){if(low>=high)return;int mid=(high&low)+((high^low)>>1);mergeSort(c,low,mid,tmp);mergeSort(c,mid+1,high,tmp);merge(c,low,mid,high,tmp);}public static void merge(int[] c,int low,int mid,int high,int[] tmp){int begin01=low;int end01=mid;int begin02=mid+1;int end02=high;int k=0;while(begin01<=end01&&begin02<=end02){if(c[begin01]<c[begin02]){tmp[k]=c[begin01];k++;begin01++;}else{tmp[k]=c[begin02];k++;begin02++;}}while(begin01<=end01){tmp[k++]=c[begin01++];}while(begin02<=end02){tmp[k++]=c[begin02++];}System.arraycopy(tmp, 0,  c,low, k);}