数据结构与算法(七)排序 选择&冒泡&快速

选择排序

public static void sort(int[] arr) {
        //在数组中选择一个最小的数,与最前面的数进行交换
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int loc = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[loc]) {
                    loc = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[loc];
            arr[loc] = temp;
        }
    }

冒泡排序

public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

快速排序

public static void sort(int[] arr) {
        //首先确认一个基数 比这个数大的放在这个数后面 比这个数小的放在这个数前面
        //4, 8, 3, 6, 2, 9 , 5 , 11 , 1
        //取第一个数为基数->4 优化:取三个数,选择其中的中间数为基数
        //从后面找比他小的数交换 -》 1, 8, 3, 6, 2, 9 , 5 , 11 , 4
        //从前面找比他大的数交换 -》 1, 4, 3, 6, 2, 9 , 5 , 11 , 8
        //从后面找比他小的数交换 -》 1, 2, 3, 6, 4, 9 , 5 , 11 , 8
        //从前面找比他大的数交换 -》 1, 2, 3, 4, 6, 9 , 5 , 11 , 8
        //再以两边分好的组作为新的数组重复以上操作,直到组内元素个数为1
        quickSort(0, arr.length - 1, arr);
    }

    public static void quickSort(int left, int right, int[] arr) {
        if (left >= right) return;
        int loc = left;
        int base = arr[loc];
        int i = left + 1; //双指针
        int j = right;
        while (i < j) {
            while (j > i) {
                if (arr[j] < base) {
                    arr[loc] = arr[j];
                    arr[j] = base;
                    loc = j;
                    break;
                }
                j--;
            }
            while (i < j) {
                if (arr[i] > base) {
                    arr[loc] = arr[i];
                    arr[i] = base;
                    loc = i;
                    break;
                }
                i++;
            }
        }
        quickSort(left, loc - 1, arr);
        quickSort(loc + 1, right, arr);
    }
# 排序 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×