算法-快速排序

 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 }

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));
    }
}