十大排序

冒泡排序

介绍:

在冒泡排序中,只有当两个元素不满足条件的时候才会需要交换,所以只有后一个元素大于前一个元素时才进行交换,这时的冒泡排序是一个稳定的排序算法。

步骤:

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

本质上是一个数组经过每轮将最大/第二大/第三大(以此类推)逐个将数放在最后/次后的算法

img

这里将{5,1,2,4,9,3}通过第一次排序后,将最大的9通过换位放在最后,同时一个数在n个数中比较大小,不需要和自身进行比较,因此只需要n-1次,在数组中也就是array.length-1次

在内部循环中,也就是第二轮循环寻找第二大数值时,最大的数与第二大的数字在第一轮已经进行过比较,所以可以省略比较步骤

当i=2时,也就是外层循环进行第三轮比较时,(第三大的数字),第三大数字与第二大(5和4)在上一轮已经进行过比较,因此省略多余步骤,(5和9依然不需要再次比较)

以此类推,可以发现重复的步骤与i的值相同,因此我们可以得出内部循环的结束条件为:array.length-1-i

程序中执行:

public static void main(String[] args) {
    int []array = {5,1,2,4,9,3};
    for (int i = 0; i < array.length-1; i++) {
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j]>array[j+1]){
                int tem = array[j];
                array[j] = array[j+1];
                array[j+1] = tem;
            }
        }
    }
    System.out.println(Arrays.toString(array));
}

image-20230808114235876

选择排序

步骤:

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

重复第二步,直到所有元素均排序完毕。

简单来说就是找到最小数字的索引,与第一个数字交换,然后从第二个开始找到最小的数(此时最小的数是第二小的数,因为最大的已经排到了它的前面)

img

在外循环中,执行的次数是array.lenth-1,因为从数组第二位开始与自身进行比较

内循环开始执行,依次与3以后的数字进行比较,直到有比3还小的数时,记录索引min

否则继续遍后面的数

当i=1时,进行第二位数字的寻找,与第一遍不同的是.此时无需再比较数组i=0,(也就是当前索引以前的数字,因为前面的数字当前已经是最小的数).也就是j只需要从i+1开始执行

最终

程序中执行

image-20230808164046300

插入排序

步骤:

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

简单说就是从数组第二个开始默认前面已经拍好序列,记录这一位数组的值,当该数大于前面数时插入,小于前面数时,将前面放索引+1也就是后移,直到该数大于前一位时插入,依次往后

img

image-20230808164852907

当i=1的时候,记录前一位的索引为preIndex,可以发现5大于3,此时直接插入,默认前面已经排好序(前面是3),

image-20230808165001901

i=2的时候,此时preIndex的值右移变为1,然后此时需要丛2开始进行插入,当2与5比较时候,小于5,因此5的索引此时后移(不必担心会改变数组原有的值,此时后移,占用的是原来为2索引为2的位置)

之后原来为5的数组的值变成2,preIndex--;(每当数组的值后移的时候-1),此时再次与preIndex的值比较,依然小于前一个数,于是再次preIndex--;并且将3的索引后移;但是此时preIndex为-1,说明以及到达数组边界,因此将2放到该位置变成{2,3,5,8,9,6}

image-20230808165724775

i=3,i=4的时候,分别插入8,9;发现都大于preIndex所对应数,因此直接插入

image-20230808170554514

i=5时,6小于9;因此将6向前继续比较,9和8依次后移,preIndex分别为4,3;最终得到排序结果

image-20230808171053918

程序中执行

image-20230808174253614

改变while中变量current与array[preIndex]大小关系可以改为升序或者降序;

当前一个值大于当前值时候,执行循环和小于时执行循环这两种情况;(循环内的操作是将前一个值后移,也就是说换句话来说会将较大(较小)的值插入在后面)

多维数组中的三种排序:

在多维数组中对多个数组某一索引进行排序

假设有这样一组二维数组

int[][] scores = {
        {90, 89, 78},
        {59, 40, 100},
        {100, 99, 80},
        {80, 61, 61},
        {60, 100, 99}
};

整体排序:

1.冒泡

如何用冒泡排序对数组中每一个数组进行排序?

循环嵌套可以最基本的完成

i为遍历每一个数组的循环,j是对数组每一个数的排序,k是每个数进行比较的次数

//遍历每一个数组
for (int i = 0; i < scores.length; i++) {
    //进行每个数组内排序(次数为基本的一维数组排序)
    
    for (int j = 0; j < scores[i].length - 1; j++) {
        for (int k = 0; k < scores[i].length-1-j ; k++) {
            if (scores[i][k] < scores[i][k + 1]) {
                int tem = scores[i][k];
                scores[i][k] = scores[i][k + 1];
                scores[i][k + 1] = tem;
            }
        }

    }

}

得到结果

image-20230810223158677

2.选择排序

for (int i = 0; i < scores.length; i++) {
    for (int j = 0; j < scores[i].length-1; j++) {
        int min =j;
        for (int k = j+1; k < scores[i].length; k++) {

            if(scores[i][k]<scores[i][min]){
                min = k;//记录最小值索引

            }

        }
        int tem = scores[i][j];
        scores[i][j] = scores[i][min];
        scores[i][min] = tem;

    }
}

组内某一元素进行排序

首先有这样三组数组

String[] names = {"安琪拉", "王昭君", "蔡文姬", "妲己", "张良"};
String[] courses = {"C++", "JAVA", "PYthon"};
int[][] scores = {
        {90, 89, 78},
        {59, 40, 100},
        {100, 99, 80},
        {80, 61, 61},
        {60, 100, 99}
};

//以及对列表输出的方法
 public static void JAVA(int scores[][], String names[], String courses[]) {
        for (int i = 0; i < scores.length; i++) {
            System.out.print(names[i] + " => "); // 输出学生姓名
            for (int j = 0; j < scores[i].length; j++) {
                System.out.print(courses[j] + ":");// 输出课程名称
                System.out.print(scores[i][j]); // 输出课程成绩
                if (j < scores[i].length - 1) {
                    System.out.print(" , ");
                }
            }
            System.out.println();
        }


    }

1.冒泡排序JAVA成绩

此处两个交换不同点是,成绩是二维数组,而name是一维数组,交换的一个是数组,一个是数组内的元素,这里需要分清楚

以及注意这里j的条件是score.length,因为相当于是把二维数组看成一维数组进行排序,JAVA成绩以外的元素我们不需要关注,也就是说本质上是比较5个Java成绩

for (int i = 0; i < scores.length - 1; i++) {
    for (int j = 0; j < scores.length - 1 - i; j++) {
        if (scores[j][1] < scores[j + 1][1]) {
            //交换数组排序
            int []tem = scores[j];
            scores[j] = scores[j + 1];
            scores[j + 1] = tem;
            //同时交换另一个数组排序
            String nam = names[j];
            names[j] = names[j+1];
            names[j+1] = nam;
        }
    }
}

运行结果

image-20230810231632059

2.选择排序

此处与选择排序不同的一点是,交换的是数组,而不是某一个数,原理依旧是把每一个数组看成若干个数

for (int i = 0; i <scores.length; i++) {
    //最小值
    int min =i;
    for (int j = i+1; j < scores.length; j++) {

        if(scores[j][2]>scores[min][2]){
            min = j;
        }
    }
    int []tem =  scores[i];
    scores[i] = scores[min];
    scores[min] = tem;
}

3.插入排序

此处原理不变,唯一改变的是带入数组元素索引,排序依旧是数组之间的排序,至少每个数组看成数字即可

int left = 0;
int right = scores.length - 1;
for (int i = 1; i < scores.length; i++) {
    int index = i - 1;
    int cur = scores[i][0];
    while (index >= 0 && cur > scores[index][0]) {

        scores[index + 1][0] = scores[index][0];
        index--;
    }
    scores[index + 1][0] = cur;
}

希尔排序

希尔排序的实质就是分组插入排序,该方法又称递减增量排序算法

思想是依然是分治法,将数组分为length/2 个 组,对每一组进行插入排序

假设有数组:

[1,4,6,3,8,9,2,23]

我们可以分为

image-20231126211013559

将这些数进行第一轮的排序得到新的数组:

[1,4,2,3,8,9,6,23]

可以看到也就是将每一组里更小的放在前面,于是我们进行第二轮:

image-20231126211428946

排序后:

[1,3,2,4,6,9,8,23]

最后进行一次增量为1的排序,得到最终排序后的答案

实现方法

实现方法有两种:

  • 交换法
  • 插入法

这里注意,插入法的效率一般远高于交换法

两者的实现核心思想其实一样,都是最外层定义的增量,只是内循环的方法不同,这里首先看一下交换法的实现

//交换法
public static void insert2(int[] arr) {
        int len = arr.length;
        for (int gap = len>>2; gap >0 ; gap/=2) {
            //遍历分支的每一个分组
            for (int i = gap; i < len; i++) {
                for (int j = i-gap; j>=0; j-=gap) {
                if (arr[j]>arr[j+1]){
                    int tem = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tem;
                }

                }
            }
        }
    }

接下来是插入法

 public static void insert3(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            //分治每一组
            for (int i = gap; i < n; i++) {
                //记录当前i的索引和所在索引的值
                int tem = arr[i]; //储存交换元素前的值
                int j;
                for ( j = i; j >= gap && arr[j - gap] > tem; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tem;
            }

        }
    }

这段插入法核心部分在于最内层的循环几个细节:

1.最重要的一点:当一组内的数不止两个时,例如[6, 5, 9, 2, 7, 1, 3, 12, 4]九个数时,4,7,6都在一组,此时在最内层循环执行的时候,j-=gap,当j为4时依然会执行异常循环,也就是相当于将最小的放在了每一组的最前面

2.tem的意义类似与插入排序中的当前指针值,当插入结束时,将tem的值赋值给更小的一个

3.对比插入排序: 希尔排序的不同就是将原来前一个换为了前 增量gap个

4.j >= gap是防止越界情况

快速排序

1.思想

类似于分治法,将数组中的数字分解为规模为原来一半的数组,并且该数组每次分治后,数组分为以某一个基准数字分为两部分的数组(左边比基准数字小右边比基准数字大)

2.图片演示

3.优缺点

1.一般的快速排序是不稳定的,其时间复杂度为 O(nlogn),其中n是所排序序列的大小。但是在选取的基准值为所排序序列的最值时(例如{12, 1, 2, 7, 9, 11, 4, 5, 6, 8})其时间复杂度会退化成O(n^2)

2.但如果采用随机选取基准值的方法,可以使得快速排序变得稳定许多,时间复杂度为 O(nlogn)

4.过程

首先要明白我们要做放事情:找到一个基准值,让它的左边的数比它小右边的数比它大,假设原数组

{6, 1, 2, 7, 9, 11, 4, 5, 10, 8};这里随便定一个基准值为6,我们要把他围绕基准值6数组排序成

{4, 1, 2, 5, 6, 11, 9, 7, 10, 8}

以下是过程

1.定义数组

public static void main(String[] args) {
    int[] arr = {6, 1, 2, 7, 9, 11, 4, 5, 10, 8};
    //调用方法排序,传递需要排序的范围,这里先从数组第一个到最后一个
    quickSort(arr, 0, arr.length - 1);
    //检查排序
    System.out.println(Arrays.toString(arr));
}
    while (left < right && arr[right] >= base) { //(条件:arr[right] >= base)
        right--;
    }
    //右指针停止后左指针开始向右移动,同理,找到比基准值大的数停止,否则一直右移(条件arr[left] <= base)
    while (left < right && arr[left] <= base) { //
        left++;
    }
    //现在已经找到左右两边开始数起,分别第一个出现的符合条件的数,也就是7和5
    //将两个数交换位置
    int tem = arr[right];
    arr[right] = arr[left];
    arr[left] = tem;

得到结果{6, 1, 2, 5, 9, 11, 4, 7, 10, 8},

此时可以交换第一次出现的一对符合条件的数,但是目标是整个数组,因此需要让这个过程继续重复执行,在这之前

有人会好奇while内left<right这个条件,这里是因为:

假设数组是{6,7,5,3}

第一次交换:{6,3,5,7}此时left指针指向3,right指向7

第二次:{6,3,5,7}中,右指针从7开始,左移到5时候,比基准值小,停止

左指针指到3以后右移到5,此时,两指针指向同一个数5,此时停止,

因此这里是left<right时候符合条件执行循环

对于arr[right] >= base左右指针是否该写=,需要考虑极端条件,比如数组:{6,6,,7,5,3}
如果写成arr[right] > base或者arr[left] <base时,当有重复值
第一次交换:
右指针指向3;左指针第二个6不复合条件,因此指向7,交换后:{6,6,3,5,7}
第二次交换:
右指针指向5,左指针指向5时两指针相遇,停止循环得到的数组{6,6,3,5,7}不符合左边小右边大的预期
因此需要写=,写==时:
第一次:{6,3,7,5,6}
第二次:{6,3,5,7,6}
将6和5交换得到预期数组{5,3,6,7,6}

这里同理,当第一次交换后,为了将每一个数排好,在外层加一个循环

while (left < right) {
    while (left < right && arr[right] >= base) {
        right--;
    }
    //右指针停止后左指针开始向右移动,同理,找到比基准值大的数停止,否则一直右移
    while (left < right && arr[left] <= base) {
        left++;
    }
    //现在已经找到左右两边开始数,分别第一个出现的符合条件的数,也就是7和5
    //将两个数交换位置
    int tem = arr[right];
    arr[right] = arr[left];
    arr[left] = tem;
}
//交换两个值
 arr[start] = arr[left]; //将指针指向赋值给第一个数6
        arr[left] = base; // 将第一个数6 给指针指向值(base=6)

结束条件是当左右指针相遇时停止,最后将两指针停止的索引对应的值与选取的基准值交换

因为left与right此时相同,因此随意选取一个进行交换

此时运行代码

接下来只需要将6左边的数和右边的数进行一个快速排序,也就是重新调用排序方法,但是改变需要排序的范围

//对左边数进行快排
quickSort(arr,start,left-1);
//对6右边进行快排
quickSort(arr,left+1,end);

并且给出递归结束条件;当不断分治到只有两个数时返回,例如数组:

{6, 1, 2, 7, 9, 11, 4, 5, 10, 8}不断进行递归:

{4, 1, 2, 5, 6, 11, 9, 7, 10, 8}

{4, 1, 2, 5, 6, 11, 9, 7, 10, 8}

{2,1,4,5,6,8,9,7,10,11} //4和11为基准

{2,1,4,5,6,8,9,7,10,11} //2和8为基准,此时2和1交换后满足条件start>=end,返回右边{8,9,7,10}继续进行快排

右边以此类推...

if(start>=end){
    return;
}

整个方法:

public static void quickSort(int[] arr, int start, int end) {
    if(start>=end){
        return;
    }

    //将定义两个指针为left和right分别在数组索引的0和length-1位置
    int left = start;
    int right = end;
    //随意选取一个基准值,这里选取第一个数,也就是索引为0;
    int base = arr[start];
    //先从右指针开始寻找比基准值小的数,如果比基准值大则继续向左移动右指针,如果找到比基准值小的数停止
    while (left < right) {
        while (left < right && arr[right] >= base) {
            right--;
        }
        //右指针停止后左指针开始向右移动,同理,找到比基准值大的数停止,否则一直右移
        while (left < right && arr[left] <= base) {
            left++;
        }
        //现在已经找到左右两边开始数,分别第一个出现的符合条件的数,也就是7和5
        //将两个数交换位置
        int tem = arr[right];
        arr[right] = arr[left];
        arr[left] = tem;
    }

    arr[start] = arr[left];
    arr[left] = base;

    //对左边数进行快排
    quickSort(arr,start,left-1);
    //对6右边进行快排
    quickSort(arr,left+1,end);
}

运行

image-20230814210738967