数据结构与算法---常见排序

277 阅读6分钟

之前看了一点关于数据结构和算法的文章,这是个充满魅力的领域,想简单总结分享一下

冒泡排序

从小到大:

  1. 初始化两个指针,分别指向第一个元素(索引0)和第二个元素(索引1);
  2. 比较相邻两个元素的大小,若右侧的元素(index+1)小于左侧(index),则交换位置,否则不变;
  3. 指针同时右移一个单位;
  4. 重复第二步,直到到达数组末尾;
  5. 末尾索引减一(已是最大),重复1,2,3,直到无须交换;

冒泡的特点:每一次轮回后(步骤4),末排序的值都会“冒”到正确的位置,然后继续轮回,继续冒泡;

冒泡实战:

public static int[] bubbleSort(int[] arr) {
    // 初始化第一次最终冒泡的位置,及最后一个索引
    int lastSortedIndex = arr.length-1;
    // 初始化设定为排序
    boolean sorted = false;

    while (!sorted) {
        sorted = true;
        for (int i = 0; i < lastSortedIndex; i++) {
            if (arr[i] > arr[i + 1]) {
                sorted = false;
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        lastSortedIndex--;
    }
    return arr;
}

public static void main(String[] args) {
    int[] arr = {2, 3, 1, 5, 4};
    System.out.println(Arrays.toString(bubbleSort(arr))); // 1,2,3,4,5
}

冒泡的效率:

比较:(N-1)+(N-2)+(N-3)+...+1

交换:最坏:(N-1)+(N-2)+(N-3)+...+1,最好:0

时间复杂度:O(N²)

选择排序

从小到大:

  1. 从左往后,记录最小值的索引,最小值初始为索引0的值,如果当前索引的值小于最小值,则更新最小的索引为当前索引,直到数组的最后一位;
  2. 将最小值与本次检查的起点交换;
  3. 初始最小值的索引进一位,重复前两步,直到排序完成(起点索引为最大索引)

选择特点:选择最小值索引。比较时,只记录索引值,不做置位操作,直到本次数组比较完毕,再进行至多一次交换,最小值将依次向后排列

选择实战:

public static int[] selectionSort(int[] arr) {
    // 从小到大排序,依次最小的值
    for (int i = 0; i < arr.length; i++) {
        // 初始化最小值的索引
        int minIdenx = i;
        for (int j = i+1; j < arr.length; j++) {
            // 当前索引值小于当前最小值,更新索引
            if (arr[j] < arr[minIdenx]) {
                minIdenx = j;
            }
        }
        // 当前最小值的索引不在起点
        if (minIdenx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdenx];
            arr[minIdenx] = temp;
        }
    }

    return arr;
}

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

选择效率:

比较:(N-1)+(N-2)+(N-3)+...+1

交换:最多:N-1,最少:0(每轮1或0次)

时间复杂度:O(N²/2) ——>忽略常数——>O(N²)

选择排序的步数大概只有冒泡的一半

插入排序

从小到大:

  1. 移出:第一轮,先将第二个元素(索引1)的值移出,保存到临时变量,并记录当前空隙位置的指针,且当前数组中第二个元素处于空隙状态;
  2. 比较并平移:临时变量与空隙左侧的值挨个比较,若空隙左侧的值大于临时变量,则该值向右移动一位,空隙自动左移(指针减一),若当前值比临时变量小,或空隙已到达最左则,平移结束;
  3. 插入:将临时变量填入空隙;
  4. 重复前三步,直到数组有序

插入特点:每轮四个步骤,移出,比较,平移,插入

插入实战:

public static int[] insertionSort(int[] arr) {
    // 从第二个元素开始移出
    for (int i = 1; i < arr.length; i++) {
        // 初始空隙所在位置的指针
        int position = i;
        // 当前移出值保存到临时变量
        int tempValue = arr[i];

        // 直到空隙移到最左侧,或当前值小于临时变量,则将临时变量插入空隙
        while (position > 0 && arr[position - 1] > tempValue) {
            // 不符合条件,将左侧值右移一位,即:将左侧的值赋给右侧,指针减一
            arr[position] = arr[--position];
        }
        // 临时变量插入当前空隙的指针
        arr[position] = tempValue;
    }
    return arr;
}


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

插入效率:

移出:N-1

比较:最多:1+2+3+...+N-1=N²/2,最少:N-1

平移:最多:N²/2,最少:0(有序)

插入:N-1

时间复杂度:O(N²+2N-2)——>简化——>O(N²),最坏、平均、最好情况:N2、N2/2、N步

快速排序

分区:

  1. 从数组从随机选取一个值,以其为轴,将比它小的值放在左边,比它大的之放到右边
  2. 放置两个指针,分别指向除轴元素的数组最左和最又的元素
  3. 左指针逐个索引向右移动,当遇到大于等于轴的值就停下来;
  4. 右指针逐个索引向左移动,当遇到小于等于轴的值就停下来;
  5. 将两个指针所指的值交换位置;
  6. 重复3,4,5,直到两个指针重合,或左指针移到右指针的右边;
  7. 将轴与左指针所在的位置交换;
  8. 当分区完成时,在轴左侧的那些值肯定比轴要小,在轴右侧的那些值肯定比轴要大

从小到大:

  1. 将数组分区,使轴到正确的位置;
  2. 对轴左右的两个子数组递归地重复1、2步,也就是说,两个子数组都各自分区,并形成各自的轴以及由轴分隔的更小的子数组。然后也对这些子数组分区,依次类推;
  3. 当分出的子数组长度为0或1时,即达到基准情形,无需进一步操作

快速特点:一次分区至少有N次比较,及数组的每个值都要与轴做比较;每次分区,左右指针豆花从两端开始靠近,直到相遇

实战:

public class TestQuickSort {
    public static int partition(int[] arr, int leftPointer, int rightPointer) {
        // 总是取最右的值作为轴
        int pivotPosition = rightPointer;
        int pivot = arr[pivotPosition];

        // 将右指针指向轴左边的一格
        rightPointer -= 1;

        while (true) {
            // 左指针只要小于轴,右移,不能超过轴
            while (arr[leftPointer] < pivot && leftPointer < pivotPosition) {
                leftPointer += 1;
            }

            // 右指针只要小于轴,左移
            while (arr[rightPointer] > pivot && rightPointer > 0) {
                rightPointer -= 1;
            }

            if (leftPointer >= rightPointer) {
                break;
            } else {
                swap(arr, leftPointer, rightPointer);
            }
        }

        // 将左指针的值与轴交换
        swap(arr, leftPointer, pivotPosition);
        // 返回左指针
        return leftPointer;
    }

    public static void swap(int[] arr, int pointer1, int pointer2) {
        int tempValue = arr[pointer1];
        arr[pointer1] = arr[pointer2];
        arr[pointer2] = tempValue;
    }

    public static int[] quickSort(int[] arr, int leftPointer, int rightPointer) {
        // 基准情形:分出的子数组长度为0或1
        if (rightPointer - leftPointer <= 0) {
            return arr;
        }

        // 将数组分成两部分,并返回分隔所用的轴的索引
        int pivotPosition = partition(arr, leftPointer, rightPointer);

        // 对轴左侧的部分递归调用quicksort
        quickSort(arr, leftPointer, pivotPosition - 1);

        // 对轴右侧的部分递归调用quicksort
        quickSort(arr, pivotPosition + 1, rightPointer);

        return arr;

    }

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

快速效率:

比较:每个值都要与轴比较

交换:在适当时候将左右指针所指的两个值交换位置

时间复杂度:一次分区,最少交换1次,最多N/2次,分区——>O(N);总共——>O(NlogN) 最好:O(NlogN),平均O(NlogN),最坏O(N²)(每次分区都是轴落在数组的开头或结尾,如已升序或降序)


参考书籍:数据结构与算法图解-【美】杰伊·温格罗