算法-快速排序

时间:2021-08-14 09:45:46

  快速排序在每一轮挑选一个基准元素,并让其他比它并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列分解成两个部分。分而治之,使用分治法。在分治法的思想下,原来数列的每一轮都被拆分成两个部分,每个部分又分别被拆分成两部分,知道其中一个部分只有一个元素不可再分。

 一、基准元素的选择

  快速排序第一个步骤是基准元素的选择,在分治的过程中,以基准元素为中心,把其他元素移动到基准元素的两边。

  极端情况:如果数列的第1个元素是最小值或者最大值,那么时间复杂度变成了O(n2

  解决方法:随机选择一个元素作为基准值。

 

二、元素的交换过程

  具体实现有两种方法:

双边循环法、单边循环法

  1.双边循环法:

  实现原理:左右两个指针同时往中间扫描,如果右边的元素小于左边的元素,则两个元素交换,直到两个指针相遇。

  第一步:选定基准元素pivot,设置左指针left和右指针right

  第二步:第1次循环,从right指针开始,让指针指向的元素与基准元素作比较。

  第三步:如果大于或等于pivot则指针左移,否则停止移动转到left指针

  第四步:如果left指针指向的元素小于或等于pivot,则指针向左移动

  第五步:如果大于,则left指针停止移动,交换left指针和right指针所指向的元素,交换后从右指针开始

  第六步:重复上面的步骤直到left指针和right指针相遇

  第七步:把pivot和两个指针指向的元素交换

  代码实现:

 1 package algorithm;
 2 
 3 import java.util.Arrays;
 4 /*
 5  * 在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到另一边,分成两个部分
 6  * 对两个部分递归进行这个操作
 7  */
 8 public class Test {
 9     public static void quickSort(int[] arr,int startIndex,int endIndex) {
10         //递归的退出条件:递归最后一层左边的元素小于或等于右边元素的位置
11         if(startIndex >= endIndex) {
12             return;
13         }
14         //得到基准元素的位置
15         
16         //取第一个位置的元素作为基准元素
17                 int pivot = arr[startIndex];
18                 int left = startIndex;
19                 int right = endIndex;
20                 
21                 /*
22                  * 第一步:选定基准元素pivot,设置左指针left和右指针right
23                  * 第二步:第1次循环,从right指针开始,让指针指向的元素与基准元素作比较。
24                  * 第三步:如果大于或等于pivot则指针左移,否则停止移动转到left指针
25                  * 第四步:如果left指针指向的元素小于或等于pivot,则指针向左移动
26                  * 第五步:如果大于,则转到right指针
27                  * 第六步:直到left指针和right指针相遇
28                  */
29                 while(left != right) {
30                     while(left<right && arr[right] > pivot) {
31                         right--;
32                     }
33                     while(left<right && arr[left] <= pivot ) {
34                         left++;
35                     }
36                     if(left<right) {
37                         int p = arr[left];
38                         arr[left] = arr[right];
39                         arr[right] = p;
40                     }
41                 }
42                 //pivot和指针重合点交换
43                 arr[startIndex] = arr[left];
44                 arr[left] = pivot;
45                 
46                 int pivotIndex =  left;
47         //根据基准元素,递归调用
48         quickSort(arr,startIndex,pivotIndex-1);
49         quickSort(arr,pivotIndex+1,endIndex);
50     }
51     /*
52      * 分治(双边循环)
53      * arr是代交换的数组
54      * startIndex是起始下标
55      * endIndex是结束下标
56      */
57     
58 
59  
60     public static void main(String[] args) {
61         int arr[] = {4,4,6,5,3,2,8,1};
62         quickSort(arr,0,arr.length-1);
63         System.out.println(Arrays.toString(arr));
64     }
65 }

  2.单边循环法:

  与双边循环不同的是,单边循环只有一个mark指针。从第二个元素开始逐个遍历每个元素,如果这个元素小于基准值,则往后继续遍历,如果这个元素大于基准值,先把mark指针后移一位,将最新遍历的元素与mark指针所在位置的元素交换位置。

  第一步:选定基准元素pivot,设置一个mark指针指向数列的起始位置。mark指针代表小于基准元素的区域边界。

  第二步:从基准元素的下一个位置开始遍历数组

  第三步:如果遍历的元素大于基准元素,就继续往后遍历,否则,需要做两件事,一把mark右移一位,二把新遍历到的元素和mark指针所在位置的元素交换位置。(mark指针右移使得小于pivot 的区域边界增大了1,交换位置是因为新遍历的元素小于pivot)

  第四步:按照以上思路,直到数列遍历完毕

package algorithm;

import java.util.Arrays;

public class SingleQuickSort {
    public static void quickSort(int[] arr,int startIndex,int endIndex) {
        //递归的退出条件:递归最后一层左边的元素小于或等于右边元素的位置
        if(startIndex >= endIndex) {
            return;
        }
        //得到基准元素的位置
        int pivotIndex = partition(arr,startIndex,endIndex);
        //根据基准元素,递归调用
        quickSort(arr,startIndex,pivotIndex-1);
        quickSort(arr,pivotIndex+1,endIndex);
    }
    /*
     * 分治(单边循环)
     * arr是代交换的数组
     * startIndex是起始下标
     * endIndex是结束下标
     * mark是标志指针
     * 算法步骤:
     * 第一步:将第数列第一个值定位基准值,将mark指针指向基准值
     * 第二步:循环遍历数列,如果遍历到的值大于基准值,则继续遍历。否则,将标志指针右移一位,交换当前遍历到的元素的值和mark指针指向的值
     * 第三步:mark指针右移使得小于pivot 的区域边界增大了1,交换位置是因为新遍历的元素小于pivot,直到数列遍历完毕
     * 
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        //取第一个位置的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for(int i = startIndex+1; i <= endIndex; i++) {
            if(arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
        
    }


    public static void main(String[] args) {
        int arr[] = {4,4,6,5,3,2,8,1};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}

三、非递归实现

 看的不是很懂....以后再写解释

 1 package algorithm;
 2 
 3 import java.util.Arrays;
 4 import java.util.HashMap;
 5 import java.util.Map;
 6 import java.util.Stack;
 7 
 8 public class AnotherQuickSort {
 9     public static void quickSort(int[] arr, int startIndex, int endIndex) {
10         //用一个集合栈来代替递归的函数栈
11         Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String,Integer>>();
12         //整个数列的起止下标,以哈希的形式入栈
13         Map<String, Integer> rootParam = new HashMap<String, Integer>();
14         rootParam.put("startIndex", startIndex);
15         rootParam.put("endIndex", endIndex);
16         quickSortStack.push(rootParam);
17         
18         //循环结束条件,栈为空
19         while(!quickSortStack.isEmpty()) {
20             //栈顶元素出栈
21             Map<String, Integer> param  = quickSortStack.pop();
22             //得到基准元素的位置
23             int pivotIndex = partition(arr,param.get("startIndex"),param.get("endIndex"));
24             //根据基准元素分成两部分,把每一部分的起止下标入栈
25             if(param.get("startIndex") < pivotIndex - 1) {
26                 Map<String, Integer> leftParam = new HashMap<String, Integer>();
27                 leftParam.put("startIndex", param.get("startIndex"));
28                 leftParam.put("endIndex", pivotIndex-1);
29                 quickSortStack.push(leftParam);
30             }
31             if(pivotIndex + 1 < param.get("endIndex")) {
32                 Map<String, Integer> rightParam = new HashMap<String, Integer>();
33                 rightParam.put("startIndex", pivotIndex+1);
34                 rightParam.put("endIndex", param.get("endIndex"));
35                 quickSortStack.push(rightParam);
36             }
37         }
38     }
39     /**
40      * 分治,单边循环法
41      * @param arr            待交换的数组
42      * @param startIndex    起始下标
43      * @param endIndex        结束下标
44      * @return
45      */
46     private static int partition(int[] arr,int startIndex,int endIndex) {
47         //取第一个位置,也可以是随机位置的元素作为基准元素
48         int pivot = arr[startIndex];
49         int mark = startIndex;
50         for(int i = startIndex+1; i <= endIndex; i++) {
51             if(arr[i] < pivot) {
52                 mark++;
53                 int p = arr[mark];
54                 arr[mark] = arr[i];
55                 arr[i] = p;
56             }
57         }
58         arr[startIndex] = arr[mark];
59         arr[mark] = pivot;
60         return mark;
61     }
62     public static void main(String[] args) {
63         int [] arr = {4,7,6,5,3,3,8,1};
64         quickSort(arr,0,arr.length-1);
65         System.out.println(Arrays.toString(arr));
66     }
67 }

 

 

代码来自《漫画算法,小灰的算法之旅》