【xsong 说算法】第一期:排序算法

本贴最后更新于 1329 天前,其中的信息可能已经水流花落

第一章:排序算法

1.1 选择排序

选择排序无论什么数据进去都是 O(N²) 的时间复杂度,唯一好处就是不占用额外的存储空间

算法思路步骤

首先先找到最大(小) 的元素,存放起始位置,重复找最小的往后排,直到所有的元素排序完毕

  • 下面是代码演示:
   /**     * 使用选择排序解题     *     * @param nums 数组     * @return 返回排序好的数组     */    public int[] sortArray(int[] nums) {        //最小值的下标        for (int i = 0; i < nums.length ; i++) {            int min = i;            for (int j = i; j < nums.length; j++) {                if (nums[j] < nums[min]) {                    min = j;               }           }            if (min != i) {                int temp = nums[i];                nums[i] = nums[min];                nums[min] = temp;           }       }        return nums;   }

选择排序的优点:交换次数最少

「选择排序」看起来好像最没有用,但是如果在交换成本较高的排序任务中,就可以使用「选择排序」(《算法 4》相关章节课后练习题)。

不要对算法带有个人色彩,在面试回答问题的时候和看待一个人和事物的时候,可以参考的回答模式是「具体问题具体分析,在什么什么情况下,用什么什么算法」。

1.2 冒泡排序

最快:当输入的数据已经是正序时(我还要你冒泡排序有何用)

最慢:当输入的数据是反序时(干嘛要用你冒泡排序呢,我是闲的吗)。

算法思路步骤

每次比较相邻的元素,如果第一个比第二个打,直接交换;直到没有任何一对数字需要比较

  • 下面是代码演示
    /**     * 使用冒泡排序解题     *     * @param nums 数组     * @return 返回排序好的数组     */    public int[] sortArray(int[] nums) {        boolean mark = true;        while (mark) {            boolean end = false;            for (int i = 0; i < nums.length - 1; i++) {                if (nums[i] > nums[i + 1]) {                    int temp = nums[i];                    nums[i] = nums[i + 1];                    nums[i + 1] = temp;                    end = true;               }           }            mark = end;       }        return nums;   }
  • 比较官方的解答
       public int[] sortArray(int[] nums) {         int len = nums.length;        for (int i = len - 1; i >= 0; i--) {            // 先默认数组是有序的,只要发生一次交换,就必须进行下一轮比较            boolean sorted = true;            for (int j = 0; j < i; j++) {                if (nums[j] > nums[j + 1]) {                    swap(nums, j, j + 1);                    sorted = false;               }           }            // 如果在内层循环中,都没有执行一次交换操作,说明此时数组已经是升序数组            if (sorted) {                break;           }       }        return nums;   }    private void swap(int[] nums, int index1, int index2) {        int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;   }

1.3 插入排序

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

算法解题步骤:

默认第一个有序,然后从后往前比较,直到找不到比自己小的,然后插进去

  • 算法实现:
   /**     * 使用插入排序解题     *     * @param nums 数组     * @return 返回排序好的数组     */    public int[] sortArray(int[] nums) {        for (int i = 1; i < nums.length; i++) {            int temp = nums[i];            int j = i;            while(j>0 && temp<nums[j-1]){                nums[j] = nums[j-1];                j--;           }            if(j != i){                nums[j] =temp;           }       }        return nums;   }

1.4 希尔排序

是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法

1.5 归并排序

该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法解题步骤:

归并排序的核心是递归,我们需要先把数组的左右两部分分别排序,然后再把左右两部分有序的数组合并到一起,形成一个有序的数组

  • 代码演示:
/** * @author song * 归并排序 对一个数组进行排序 */ public class Code02_MerageSort {    public static void main(String[] args) {        int[] arr = new int[]{3, 5, 1, 4, 9, 7};        process(arr, 0, arr.length - 1);        System.out.println(Arrays.toString(arr));   }    public static void process(int[] arr, int L, int R) {        if (L == R) {            return;       }        int mid = L + ((R - L) >> 1);        process(arr, L, mid);        process(arr, mid + 1, R);        merage(arr, L, mid, R);   }    public static void merage(int[] arr, int L, int M, int R) {        int[] help = new int[R - L + 1];        int i = 0;        int p1 = L;        int p2 = M + 1;        //说明左右区间都有数        while (p1 <= M && p2 <= R) {            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];       }        //只有左侧有数        while (p1 <= M) {            help[i++] = arr[p1++];       }        //同理只有右侧有数        while (p2 <= R) {            help[i++] = arr[p2++];       }        for (int j = 0; j < help.length; j++) {            arr[L + j] = help[j];       }   } }

****ps:有一个经典的例题LeetCode 剑指 offer51 我建议每次复习归并排序的时候,都去做一遍这个题【在做这个题的时候,其核心部分在判断临界值的时候一定要小心】

1.6 快速排序

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

算法思想

  1. 从数组中挑出来一个元素、称为基准(pivot)
  2. 重新排序,比基准小的在基准前面,泛指比基准大的在后面
  3. 递归,以基准为标准,左右两边的数分别执行一二步骤img
  • 代码实现
import java.util.Random; public class Solution {    // 快速排序 3:三指针快速排序    /**     * 列表大小等于或小于该大小,将优先于 quickSort 使用插入排序     */    private static final int INSERTION_SORT_THRESHOLD = 7;    private static final Random RANDOM = new Random();    public int[] sortArray(int[] nums) {        int len = nums.length;        quickSort(nums, 0, len - 1);        return nums;   }    private void quickSort(int[] nums, int left, int right) {        // 小区间使用插入排序        if (right - left <= INSERTION_SORT_THRESHOLD) {            insertionSort(nums, left, right);            return;       }        int randomIndex = left + RANDOM.nextInt(right - left + 1);        swap(nums, randomIndex, left);                int pivot = nums[left];        int lt = left;        int gt = right + 1;        int i = left + 1;        while (i < gt) {            if (nums[i] < pivot) {                lt++;                swap(nums, i, lt);                i++;           } else if (nums[i] == pivot) {                i++;           } else {                gt--;                swap(nums, i, gt);           }       }        swap(nums, left, lt);        // 注意这里,大大减少了两侧分治的区间        quickSort(nums, left, lt - 1);        quickSort(nums, gt, right);   }    /**     * 对数组 nums 的子区间 [left, right] 使用插入排序     *     * @param nums 给定数组     * @param left 左边界,能取到     * @param right 右边界,能取到     */    private void insertionSort(int[] nums, int left, int right) {        for (int i = left + 1; i <= right; i++) {            int temp = nums[i];            int j = i;            while (j > left && nums[j - 1] > temp) {                nums[j] = nums[j - 1];                j--;           }            nums[j] = temp;       }   }    private void swap(int[] nums, int index1, int index2) {        int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;   } }

LeetCode 实战

  • 算法
    425 引用 • 254 回帖 • 24 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3203 引用 • 8217 回帖 • 2 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...