美文网首页
快速排序

快速排序

作者: 小北觅 | 来源:发表于2018-11-10 11:41 被阅读1次

    morewindows的快速排序讲解,非常好

    不稳定
    O(N*LogN)

    package sort;
    //快速排序
    public class QuickSort {
    
        public static void main(String[] args) {
    
            int[] array = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
            int[] arr1 = { 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 };
            quickSort(array, 0, array.length-1);
    //      int partition = partition(arr1, 0, arr1.length - 1);
    //      System.out.println("partition:" + partition);
    //      for (int i : arr1) {
    //          System.out.println(i);
    //      }
    
             int partition = partition(array, 0, array.length-1);
             System.out.println("partition:"+partition);
             for (int i : array) {
             System.out.println(i);
             }
            
        }
    
        static void quickSort(int[] array, int begin, int end) {
            if (begin < end) {
                int i = partition(array, begin, end);
                quickSort(array, begin, i - 1);
                quickSort(array, i + 1, end);
            }
    
        }
    
        static int partition(int[] array, int start, int end) {
    
            int low = start;
            int high = end;
    
            int key = array[low];
    
            while (low < high) {
    
                while (low < high && array[high] >= key)
                    high--;
    
                if (low < high) {
                    array[low] = array[high];
                    low++;
                }
    
                while (low < high && array[low] <= key)
                    low++;
    
                if (low < high) {
                    array[high] = array[low];
                    high--;
                }
            }
            array[low] = key;
            return low;
        }
    }
    

    相关文章

      网友评论

          本文标题:快速排序

          本文链接:https://www.haomeiwen.com/subject/dzrzxqtx.html