关于冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序的总结。

冒泡排序

思路:两两比较,大的沉底。i是轮数,在进行第i轮的时候确定了最大的i个值;如果一轮下来都没有交换证明已经有序

时间复杂度:O(n²),最好时间复杂度O(n)

空间复杂度:O(1)

稳定性:可以实现成稳定的

写冒泡排序自己的错误:

  • 因为循环中有j+1作为索引,所以j的边界结束值是j == nums.length - 2 - i,而不是nums.length - 1 - i
public static void bubbleSort(int[] nums) {
    boolean sorted = true;
    for (int i = 0; i <= nums.length - 1; i ++) {
        for (int j = 0; j <= nums.length - 2 - i; j ++) {
            if (nums[j] > nums[j + 1]) {
                sorted = false;
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
            }
        }
        if (sorted) return;
    }
}

插入排序

思路:像小孩子插扑克牌一样,要一张张比,把第1张和第0张比较,把第2张和[0,1]张比较,从后往前把第i张牌和第i-1,i-2...张牌比较,比前面的小就和前面的数交换位置,插第i张的时候前面i-1张都已经有序了

时间复杂度:O(n²),最好时间复杂度O(n)

空间复杂度:O(1)

稳定性:可以实现成稳定的

public static void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i ++) {
        for (int j = i; j >= 1; j --) {
            if (nums[j] < nums[j - 1]) {
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
    }
}

选择排序

思路:遍历[0,n-1]位置选出最小的和nums[0]交换位置,再遍历[1,n-1]位置选出第二小的和nums[1]交换...第i轮(i从0开始)选数的时候前i个位置[0,i-1]的数都已经是在正确的位置上了,待选的范围是[i, n-1],第i轮选完[0.i]都在正确位置上了

时间复杂度:O(n²),最好时间复杂度O(n²)

空间复杂度:O(1)

稳定性:无法实现成稳定的

写选择排序自己的错误:

  • 在全局定义了minIndex的起始值是0,后面忘记了应该是i,而不是一直是0,应该把minIndex放在for循环中赋值,每次进入for循环都有不同的minIndex
public static void selectionSort(int[] nums) {
    for (int i = 0; i <= nums.length - 2; i ++) {
        int minIndex = i;
        for (int j = i; j < nums.length; j ++) {
            minIndex = nums[j] < nums[minIndex] ? j : minIndex;
        }
        if (minIndex != i) {
            int tmp = nums[i];
            nums[i] = nums[minIndex];
            nums[minIndex] = tmp;
        }
    }
}

归并排序

思路:分治后从下往上两两归并,借助mergeSortPart分别将左边和右边sort,再将两边merge起来。

时间复杂度:O(nlogn),最好时间复杂度O(nlogn)

空间复杂度:O(n)

稳定性:可以实现成稳定的

写归并排序的时候自己的几个错误:

  • p2的起始值是mid + 1而不是mid
  • 前面i已经在全局中被定义了,后面写for (int i = 0; i < nums.length; i ++)又习惯性地加了int,重复定义了变量。
  • int mid = lo + ((hi - lo) >> 1);要注意>>的优先级。
  • 注意i的范围是[0, n - 1],nums下标的范围是[lo, hi]
public static void mergeSort(int[] nums) {
    if (nums == null || nums.length < 2) return;
    mergeSortPart(nums, 0, nums.length - 1);
}

public static void mergeSortPart(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + ((hi - lo) >> 1);
    mergeSortPart(nums, lo, mid);
    mergeSortPart(nums, mid + 1, hi);
    merge(nums, lo, mid, hi);
}

public static void merge(int[] nums, int lo, int mid, int hi) {
    int length = hi - lo + 1;
    int[] helper = new int[length];
    int p1 = lo, p2 = mid + 1;
    int i = 0;

    while (p1 <= mid && p2 <= hi) {
        helper[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
    }
    while (p1 <= mid) {
        helper[i++] = nums[p1++];
    }
    while (p2 <= hi) {
        helper[i++] = nums[p2++];
    }

    for (i = 0; i < length; i ++) {
        nums[lo + i] = helper[i];
    }
}

快速排序

思路:

  • partition函数:随机取一个基准点,把基准点和最后一个数交换,partition函数的目的是要将[lo,hi]从左到右分为小于基准点区域、等于基准点区域、大于基准点区域三个区域,然后返回等于区域的左右下标给quickSortPart函数。partition的实现看成往小于区域和大于区域发货。
  • quickSortPart函数:调用partition函数,partition后返回等于区域下标后在小于区域和大于区域中递归调用自己,直到小于区域和大于区域都只有一个数。
  • quickSort函数:调用quickSortPart函数,实现快排。

时间复杂度:O(nlogn)

空间复杂度:O(logn)(因为递归深度是logn,用用来记录切分点)

稳定性:无法实现成稳定的

记一个结论 随机得到一个在[lo, hi]之间的数:(int)(lo + length * Math.random()) = (int) (lo + (hi - lo + 1) * Math.random())

注意:用位运算交换两个数有一个问题,就是当lo == hi的时候,是同一个数,就会将这个数清零(nums[lo] == nums[hi]不会,lo == hi会)

public static void swap(int[] nums, int lo, int hi) {
    if (lo == hi) return; // 要排除lo == hi的情况
    nums[lo] = nums[lo] ^ nums[hi];
    nums[hi] = nums[lo] ^ nums[hi];
    nums[lo] = nums[lo] ^ nums[hi];
}

写快排的时候自己的几个错误:

  • swap(int[] nums, int lo, int hi)函数没有去除lo == hi的情况,使得一旦同一个数自己和自己发生交换就会清零。
  • swap(nums, (int) (lo + length * Math.random()), hi);写成swap(nums, int(lo + length * Math.Random()), hi);一个是类型转换的括号要打在int上,一个是random()是小写。
  • 不要忘记随机选一个数和最后一个数nums[hi]换作为基准点,nums[hi]一直呆在大于队列中,最后不要忘了把nums[hi]nums[more]调换,放回到等于队列中。
public static void quickSort(int[] nums) {
    if (nums == null || nums.length < 2) return;
    quickSortPart(nums, 0, nums.length - 1);
}

 public static void quickSortPart(int[] nums, int lo, int hi) {
     if (lo >= hi) return;
     int[] equalRange = partition(nums, lo, hi);
     quickSortPart(nums, lo, equalRange[0] - 1);
     quickSortPart(nums, equalRange[1] + 1, hi);
 }

 public static int[] partition(int[] nums, int lo, int hi) {
     int length = hi - lo + 1;
     // 随机选取基准点和最后一个数交换
     // Math.Random() [0,1) -> (hi-lo+1) * Math.Random() [0,hi-lo+1)
     // lo + (hi-lo+1) * Math.random() [lo, lo+hi-lo+1)=[lo, hi+1)=[lo,hi]
     swap(nums, (int) (lo + length * Math.random()), hi);
     int less = lo - 1;
     int more = hi; // more从hi开始,保护nums[hi]在大于区域中不会被换掉,最后再替换
     int cur = lo;
     while (cur < more) {
         // 小于的话,和小于边界右边的第一个数交换位置,less++
         // 小于边界右边的第一个数一定是等于区域的数,所以直接cur++
         if (nums[cur] < nums[hi]) {
             swap(nums, cur ++, ++ less);
             // 等于的话,直接cur++就可以了
         } else if (nums[cur] == nums[hi]) {
             cur ++;
             // 大于的话,和大于边界左边的第一个数交换位置,more--
             // 大于边界左边的第一个数是未知的,所以要再考察cur不能++
         } else {
             swap(nums, cur, -- more);
         }
     }
     swap(nums, more ++, hi);
     return new int[]{less + 1, more - 1};
 }

 public static void swap(int[] nums, int lo, int hi) {
     if (lo == hi) return;
     nums[lo] = nums[lo] ^ nums[hi];
     nums[hi] = nums[lo] ^ nums[hi];
     nums[lo] = nums[lo] ^ nums[hi];
 }

堆排序

完全二叉树 = 堆 = 优先级队列

思路:

  • 完全二叉树是一种逻辑结构,实际存储在数组中,nums[i]的左节点是nums[2 * i + 1],右节点是nums[2 * i + 2],父节点是nums[(i - 1) / 2]
  • heapInsert()建堆函数:当堆中插入一个新节点(第i号节点nums[i])时,向上和父节点比大小,若大则换,不断调整成大根堆
  • heapify()调整函数:节点上的某个值变小后要下沉,若左右两个孩子中最大的比我大则和我交换,不断下沉直到[0, heapSize - 1]范围恢复成一个大根堆。
  • heapSort()堆排序:每次堆的头和堆的最后一个数交换,最后一个最大的数固定,heapSize --,由于头被换成了一个比较小的数,于是要做一次heapify()调成大根堆,再重复每次将堆的头和堆的最后一个数交换。

时间复杂度:O(nlogn)

空间复杂度:O(1)

稳定性:无法实现成稳定的

记一个结论:把完全二叉树逻辑结构存在数组实际结构中,nums[i]的左节点是nums[2 * i + 1],右节点是nums[2 * i + 2],父节点是nums[(i - 1) / 2]

    public static void heapInsert(int[] nums, int i) {
        while (nums[i] > nums[(i - 1) / 2]) {
            swap(nums, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    public static void heapify(int[] nums, int i, int heapSize) {
        int leftIndex = 2 * i + 1;
        while (leftIndex <= heapSize - 1) {
            int maxIndex = leftIndex + 1 <= heapSize - 1 && nums[leftIndex + 1] > nums[leftIndex] ? leftIndex + 1 : leftIndex;
            maxIndex = nums[maxIndex] > nums[i] ? maxIndex : i;
            if (maxIndex == i) return;
            swap(nums, maxIndex, i);
            i = maxIndex;
            leftIndex = 2 * i + 1;
        }
    }

    public static void heapSort(int[] nums) {
        if (nums == null || nums.length < 2) return;
        for (int i = 1; i < nums.length; i ++) {
            heapInsert(nums, i);
        }
        int heapSize = nums.length;
        while (heapSize >= 2) {
            swap(nums, 0, -- heapSize);
            heapify(nums, 0, heapSize);
        }
    }

    public static void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }

results matching ""

    No results matching ""