Leetcode排序专题

排序

1.冒泡排序

一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为元素回经由交换慢慢”浮”到数列的顶端

思路:

1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个
2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数
3. 针对所有的元素重复以上的步骤,除了最后一个
4. 重复步骤1-3,直到排序完成

代码实现:

public int[] sortArray(int[] nums){
    if (nums.length == 0) return nums;

    for (int i=0;i<nums.length;i++){
        for (int j=0;j<nums.length-1-i;j++){
            if (nums[j+1]<nums[j]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }

    return nums;
}

2.选择排序

选择排序的思想其实和冒泡排序类似,选择排序可以看成冒泡排序的优化

思路:

1. 找到数组中小的那个元素
2. 将他和数组中第一个元素交换位置
3. 在剩下元素中找到最小的元素,将它与数组中的第二个元素交换位置。如此往复,直到将整个数组排序

代码实现:

public int[] sortArrays(int[] nums){
    if (nums.length == 0) return nums;

    for (int i=0;i<nums.length;i++){
        int minIndex = i;   //最小元素的下标

        for (int j=i;j<nums.length;j++){
            if (nums[j] < nums[minIndex]){
                minIndex = j;
            }
        }

        int temp = nums[minIndex];
        nums[minIndex] = nums[i];
        nums[i] = temp;
    }

    return nums;
}

赏

谢谢你请我吃糖果