冒泡排序和鸡尾酒排序和快速排序

稳定性：

• 稳定排序：相同值得元素 在排序后仍然保持着排序前的顺序
• 不稳定排序： 相同值的元素 在排序后 打乱了排序前的顺序

冒泡排序

冒泡排序 （bubble sort）： 一种基础的交换排序,将相邻两个两两比较，当一个元素大于右侧相邻元素时，交换他们的位置，，
优化：

1. 当一次循环中两两比较，，都不需要交换的时候，说明数组是有序的，，就可以提前结束…设置一个 isSorted
2. 记录一次循环中，最后一次交换的位置lastChangeIndex，，，这个位置之后的元素，两两比较是不需要交换的，，，所以，循环遍历到这个位置就行

/**
 * 1. 如果后面循环的元素是 有序的，，那么就不用比较了
 * 2. 在比较的时候，两两比较，，如果从某一个循环的某一个点开始 两两比较不再被交换[后面的元素不需要被比较]
 */
public class BubbleSort {
    public static void sort(int[] array){

        // 每次只需要比较到这个位置就可以，，后面的都不再被交换
        int sortBorder = array.length-1;
        // 最后一次被交换的点 ，，， 这个点之后的元素不用再做比较
        int lastChangeIndex = 0;

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

            // 假设是有序的，，，一旦交换表示不是有序的
            boolean  isSorted = true;

            // 最后一个不让他取到
            for (int j = 0; j < sortBorder; j++) {
                if(array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;

                    // 存在交换，， 标记设置为false
                    isSorted = false;

                    lastChangeIndex = j;
                }
            }

            if(isSorted){
                break;
            }
            sortBorder = lastChangeIndex;
        }
    }


    public static void main(String[] args) {
        int[] arr = {3,4,2,1,5,6,7,8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

鸡尾酒排序

冒泡排序是从左到右遍历，，
鸡尾酒排序是 先从左到右，，同时从右到左，，，最外层的循环次数就会少一半

/**
 * 鸡尾酒排序
 */
public class CockTailSort {
    public static void sort(int[] array){
        //  两边都开始比较，，，外层只需要比较 array.length/2
        for (int i = 0; i < array.length / 2; i++) {

            // 是否有序
            boolean isSorted = true;

            // 从左往右比较
            for (int j = i; j < array.length - i - 1; j++) {
                if(array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    // 设置标记为 false
                    isSorted = false;
                }
            }

            if(isSorted){
                break;
            }


            isSorted = true;
            // 从右往左比较
            for (int j = array.length-i-1; j > i; j--) {
                if(array[j] < array[j-1]) {
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }

        }
    }


    public static void main(String[] args) {
        int[] arr = {3,4,2,1,5,6,7,8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

快速排序

分治法
会在每一轮，挑选一个基准元素 pivot，，将比他大的元素移动到右边，将比他小的元素移动到左边，，从而将数列拆解成两个部分，，然后递归继续分
时间复杂度 O(nlogn)
元素的交换：

• 双边循环法 ： 设置基准元素为第一个元素，，左指针，，右指针，，pivot。。。如果右指针指向的元素大小，，大于pivot，，右指针向左移动一位，，如果右指针指向元素小于 pivot，，停止移动，，看左指针，，如果左指针指向元素 小于等于pivot,让他移动，，否则将 左指针指向元素 和 右指针指向元素 交换,当左指针和右指针指向同一个位置，表示数组已经交换完了，，，最后将这个位置的值和第一个元素的值[基准元素] 交换
• 单边循环法: 设置基准元素为第一个元素，，，如果遇到比这个基准元素还要小的元素，，，指针+1,将这个元素和当前指针指向的元素进行交换，，，，那么这个指针指向的索引，和他之前的索引都是比这个基准元素小的元素，，，最后，，将指针所指向的元素和基准元素交换

/**
 * 快速排序  pivot
 */
public class QuickSort {


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

    }


    /**
     * partition 分割 双边循环法
     * @param arr  要排序的数组
     * @param startIndex 开始索引
     * @param endIndex  结束索引
     * @return  返回基准点 的索引
     */
    private static int partition(int[] arr,int startIndex, int endIndex){
        int pivot =  arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while(left != right){
            while (arr[right] > pivot && left<right){
                right--;
            }
            // 左边的 小于等于
            while (arr[left] <= pivot && left <right){
                left++;
            }

            // 交换 left 和 right 指向的元素
            if(left < right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // pivot 和 指针重合的点 交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return  left;
    }


    /**
     * 分治 （单边循环法）  mark标记之前的都是在 基准元素  左边的元素
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return  基准元素的 坐标
     */
    private static int partition02(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 temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        // 将最后mark的位置  和 基准元素交换
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;

        return mark;
    }


    public static void quickSort02(int[] arr,int startIndex,int endIndex){

        if(startIndex >= endIndex){
            return;
        }

        // 得到基准元素
        int pivotIndex = partition02(arr, startIndex, endIndex);

        quickSort02(arr,startIndex,pivotIndex-1);
        quickSort02(arr,pivotIndex+1,endIndex);

    }

    public static void main(String[] args) {
        int[] arr = {3,4,7,1,5,6,2,8};
//        int pivotIndex = partition(arr, 0, arr.length-1);
//        System.out.println("pivotIndex = " + pivotIndex);
        quickSort02(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

递归使用 栈 代替：

public class QuickSortWithStack {
    public static void quickSort(int[] arr,int startIndex,int endIndex){
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();

        HashMap<String, Integer> rootParam = new HashMap<>();
        rootParam.put("startIndex",startIndex);
        rootParam.put("endIndex",endIndex);

        quickSortStack.push(rootParam);
        // 当 栈 为空的时候， 跳出循环
        while (!quickSortStack.isEmpty()){
            // 从 栈 中取元素，，获取 起止下标
            Map<String, Integer> param = quickSortStack.pop();

            int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));

            // 可以继续分
            if(param.get("startIndex") < pivotIndex-1){
                HashMap<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex",param.get("startIndex"));
                leftParam.put("endIndex",pivotIndex-1);
                quickSortStack.push(leftParam);
            }

            if(param.get("endIndex") > pivotIndex+1){
                HashMap<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex",pivotIndex+1);
                rightParam.put("endIndex",param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }


    /**
     * 分治，，（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return 基准元素 索引位置
     */
    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 temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;

        return mark;
    }

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69