Java数据结构与算法——快速排序-青岛软件培训-Java培训-Python培训学校-万码学堂

2022-03-20 16:32

Java数据结构与算法——快速排序

王姐姐

JavaEE

(1015)

(0)

1、快速排序思想及原理

事实上，快速排序是堆冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割为两部分，第一部分所有数据比第二部分的所有数据小，按照这种思路将两部分数据再次分别进行快速排序，可以使用递归完成，最终使得整个数据序列有序。

具体来讲，在待排数据中找一个基准数据（通常取第一个数），接下来将待排数据中比基准数据小的放在待排数据的左侧，将比待排数据中比基准数据大的放在待排数据右侧。此时，左右两个分区的元素相对有序，接着采用上述思路继续对左右两个分区继续排序，直到各分区只有一个元素位置。这里用到了一个典型的分治思想。下面举例说明：

待排序列依次为47、29、71、99、78、19、24、47。为了区分两个47，将后面的47下面增加一个下划线。

步骤：
1、选取一个基准数，一般选第0个元素47。
2、将比基准数小的移动到左侧，比基准数大的移动到右侧，相等的不移动，此时基准数位置为K。
3、对左右两侧重复步骤1和步骤2，直到左右侧细分到只有一个元素。

快排的难点也就是在第2步，怎么移动各个数据？
<1> 首先从数列的右边开始往左找，设下标为i，也就是i--操作，找到第一个比基准数小的值，让他与基准数交换；
<2> 接着开始从左往右找，设下标为j，也就是j++，找到第一个比基准数大的值，让他与基准数交换位置；
<3> 重复1和2，直到i和j相遇时结束，最后基准值所在位置为k。

2、java快排代码

public class QuickSort {    private int[] array;    public QuickSort(int[] array){        this.array = array;
    }    
    public void printSort(){        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }    
    public void sort(){
        quicksort(array,0,array.length -1);
    }    
    private void quicksort(int[] array,int begin,int end){        if(begin<end){  //i和j没相遇之前比较各数据与基准值大小
            int base = array[begin];  //取第一个值为基准值
            int i = begin;  //左标记为i
            int j = end;    //右标记为j
            
            //一趟排序，找到比基准值大的在基准值右，比基准值小的在基准值左
            while(i<j){                //从右往左扫描
                while(i<j && array[j]>base){ //从右往左扫，如果元素比基准值大
                    j--;  //则右边标记--，直到找到第一个比基准值小的，停止扫描
                }                if(i<j){
                    array[i]=array[j];  //交换右扫描第一个比基准值小的数
                    i++;  //i标记右移一位
                }                //从左往右扫描
                while(i<j && array[i]<base){//从左往右扫，如果元素比基准值小
                    i++;  //则左标记++，直到找到第一个比基准值大的，停止扫描
                }                if(i<j){
                    array[j]=array[i];  //交换左扫描第一个比基准值大的数
                    j--;  //j标记左移一位
                }
            }  //此时基准值左右两侧相对有序
            
            array[i] = base;  //此时i为中间位置k
            
            quicksort(array,begin,i-1);  //左侧按照快排思路，递归
            
            quicksort(array,i+1,end);    //右侧按照快排思路，递归
        }
    }    
}

测试代码

public class SortTest {    public static void main(String[] args) {
        teseQuickSort();
    }    private static void teseQuickSort(){        int[] array = {3,5,7,3,8,9,6,1,0};        QuickSort qs = new QuickSort(array);
        qs.sort();
        qs.printSort();
    }
}