Java重点之基于比较的七大排序

public static void insertSort( int [] array) {

         //该循环实现对整个数组的遍历操作

         for ( int i = 1 ; i < array.length; ++i) {

             //记录将被插入的元素(i下标元素)

             int tmp = array[i];

             //j指向i的前一个元素

             int j = i - 1 ;

             for (; j >= 0 ; j--) {

                 //如果j指向的元素比被插入元素大，就往后移一位

                 if (array[j] > tmp) {

                     array[j + 1 ] = array[j];

                 } else { //否则就找到了插入位置，跳出该循环

                     break ;

                 }

             }

             //j+1即为插入位置

             array[j + 1 ] = tmp;

         }

}

public static void shellSort( int [] array) {

         int gap = array.length;

         while (gap > 1 ) {

             //gap为1时，就是直接插入排序

             gap = gap / 3 + 1 ;

             shell(array, gap);

         }

}

public static void shell( int [] array, int gap) {

         for ( int i = gap; i < array.length; ++i) {

             int tmp = array[i];

             int j = i - gap;

             for (; j >= 0 ; j -= gap) {

                 if (array[j] > tmp) {

                     array[j + gap] = array[j];

                 } else {

                     break ;

                 }

             }

             array[j + gap] = tmp;

         }

}

public static void selectSort( int [] array){

     for ( int i = 0 ;i<array.length;++i){

         for ( int j = i+ 1 ;j<array.length;++j){

             if (array[j]<array[i]){

                 int tmp = array[i];

                 array[i] = array[j];

                 array[j] = tmp;

             }

         }

     }

}

public static void heapSort( int [] array) {

         createHeap(array); //建大堆

         int end = array.length - 1 ;

     //将堆头元素与堆尾元素互换位置，就将最大元素放到了最后一位，舍去最后一位小标重新将堆向下调整；直到堆为空，数组中元素就排序完成。

         while (end >= 0 ) {

             int tmp = array[ 0 ];

             array[ 0 ] = array[end];

             array[end] = tmp;

             end--;

             siftDown(array, 0 , end);

         }

     }

     //从小到大排序，建一个大堆

     public static void createHeap( int [] array) {

         for ( int parent = (array.length - 1 ) / 2 ; parent >= 0 ; parent--) {

             siftDown(array, parent, array.length- 1 );

         }

     }

     //向下调整大堆

     public static void siftDown( int [] array, int root, int end) {

         int parent = root;

         int child = 2 * parent + 1 ;

         while (child <= end) {

             if (child + 1 <= end && array[child] < array[child + 1 ])

                 child++;

             if (array[parent] < array[child]) {

                 int tmp = array[parent];

                 array[parent] = array[child];

                 array[child] = tmp;

                 parent = child;

                 child = parent * 2 + 1 ;

             } else {

                 break ;

             }

         }

     }

public static void bubbleSort( int [] array) {

     //最外层循环为比较的趟数

        for ( int i = 0 ; i < array.length - 1 ; ++i) {

            //flag是为了判断接下来的循环是否有必要进行

            boolean flag = false ;

            //内层循环为每趟比较的次数

            for ( int j = 0 ; j < array.length - 1 - i; ++j) {

                if (array[j] > array[j + 1 ]) {

                    int tmp = array[j];

                    array[j] = array[j + 1 ];

                    array[j + 1 ] = tmp;

                    flag = true ;

                }

            }

            //flag==false说明这趟循环没有交换数据，也就是说数组已经有序，可以直接返回。

            if (flag == false ) return ;

        }

    }

public static void quickSort( int [] array, int l, int r) {

         if (l >= r) return ;

     //因为用do while（）循环，所以先将左右指针向两边移动一位

         int i = l - 1 , j = r + 1 ;

     //取数组中间元素的值作为这个分割点

         int mid = array[(l + r)>> 1 ];

         while (i < j) {

             //左边的数小于中间值，指针向右移动

             do ++i; while (array[i] < mid);

             //右边的数大于中间值，指针向左移动

             do --j; while (array[j] > mid);

             //两个指针停下后交换元素

             if (i < j) {

                 int tmp = array[i];

                 array[i] = array[j];

                 array[j] = tmp;

             }

         }

     //递归左半部分

         quickSort(array, l, j);

     //递归右半部分

         quickSort(array, j + 1 , r);

     }

public static void mergeSort( int [] array){

        mergerSortInternal(array, 0 ,array.length- 1 );

    }

    public static void mergerSortInternal ( int [] array, int l, int r){

        if (l>=r)    return ;

        int mid = (l+r)>> 1 ;

        //递归左半部分

        mergerSortInternal(array,l,mid);

        //递归右半部分

        mergerSortInternal(array,mid+ 1 ,r);

        //归并

        merge(array,l,mid,r);

    }

    public static void merge( int [] array, int l, int mid, int r){

        int s1 = l,e1 = mid;

        int s2 = mid+ 1 , e2 = r;

        int [] tmp = new int [r-l+ 1 ];

        int k = 0 ;

        //比较两个有序小数组元素，将小的元素放到新数组前面，大的元素放到新数组后面

        while (s1<=e1 && s2<=e2){

            if (array[s1]<array[s2]){

                tmp[k++] = array[s1++];

            } else {

                tmp[k++] = array[s2++];

            }

        }

        //处理剩余元素

        while (s1<=e1)   tmp[k++] = array[s1++];

        while (s2<=e2)   tmp[k++] = array[s2++];

        //将排完序的新数组元素放回原数组中

        for ( int i = 0 ;i<tmp.length;++i){

            array[i+l] = tmp[i];

        }

    }