排序算法

Source

冒泡排序

/**
 * Created by yan on 2019/1/21.
 */
public class Demo {
    public static void main(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;

                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

详解:
在这里插入图片描述
假如我们对 54321 这五个数字进行排序,需要两次循环
1.A行的数字5和之后的数字以此比较,比出最大数字需要4次,大数字向后派(比出最小同理)
2.将五个数字按从小到大排序完成,需要经历A–>B–>--------->E,即4次 =(5-1)次
3.内循环是将第一位数和之后的数字依次比较大小,最大需要(数字个数-1)次(浮动,依次减小)
4.外循环是将每一个数字都进行步骤3操作,需要(数字个数-1)次
因此外循环:

 for (int i = 0; i < arr.length-1; i++){
 }

对步骤3进一步解释:
1)当从A—>B时,需要进行5-1次比较,
2)当从B—>C时,需要进行5-1-1次比较,
3)当从C—>D时,需要进行5-1-1-1次比较,
因此步骤3的次数和外循环的第几次循环相关,即第一次循环5-1次(最大次数),从第二次循环开始,每次-1,
所以内循环:

 for (int j = 0; j < arr.length-1-i; j++) {
 }

选择排序

选择排序的思路和冒泡排序有些相似
冒泡排序是将第一个数与之后的所有数依次进行比较,并替换。
选择排序是将第一个数与第二个数进行比较,之后还是第一个位置上的数与第三位置上的数进行比较,并替换。

/**
 * Created by yan on 2019/1/21.
 */
public class Demo {
    public static void main(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};

        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i]>arr[j]){
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

讲解如图:
在这里插入图片描述
从图可知,这种排序方式可以在一轮排序后将最小的数字排到第一位(降序反之),需要进行5 - 1 = 4次循环
由于第一轮始终是第一位的数字和2.3.4.5.位置上的数字进行比较,所以内循环中的初始值应该是i+1(i 保证了每轮始终保持同一位置的需求,+1满足了"5-1 = 4"次循环的需求)

插入排序

快速排序

希尔排序

堆排序

归并排序