Java 排序方法(用java实现选择排序)

1. 插入排序的介绍：2.插入排序的代码实现：3. 代码时间分析：4. 复杂度分析

下面是插入排序学习笔记，包括算法演示，代码讲解，复杂度的分析

插入排序是是《算法导论》中学习的第一个算法。对于 少量元素的排序，插入排序比较高效。《算法导论》书中是这样比喻插入排序的：

插入排序就像人们在玩扑克时对手中的扑克牌进行排序：
     ~~~~     开始时，左手的排为 空 ，每次用右手从牌堆中摸取一张牌，并将其插入左手中的正确位置。
     ~~~~     为了找到这个正确的位置，我们在左手的牌中，从右到左，依次进行比较，直到找到合适的位置，将其 插入。

下面来看一下，插入排序的动图：

下面对这个排序过程进行模型化：对于数组： n u m s [ n ] nums[n] nums[n]，我们对其进行从小到大排序
假设现在我们排序到了第 i i i 个数，现在，我们让： k e y key key 来代替 n u m s [ i ] nums[i] nums[i]
然后我们现在另 j = i − 1 j=i-1 j=i−1 然后依次向前遍历，进行比较，比较： n u m s [ j ] 与 n u m s [ j − 1 ] 的 大 小 ： i f n u m s [ j ] > k e y n u m s [ j + 1 ] = n u m s [ j ] , j − − i f n u m s [ j ] ≤ k e y   ∣ ∣   j = = 0 n u m s [ j + 1 ] = k e y nums[j]与nums[j-1]的大小：begin{array}{lll}if &nums[j]>key&nums[j+1]=nums[j],j--\if&nums[j] leq key~||~j==0&nums[j+1]=keyend{array} nums[j]与nums[j−1]的大小：ifif​nums[j]>keynums[j]≤key ∣∣ j==0​nums[j+1]=nums[j],j−−nums[j+1]=key​
先来理解第一个 i f if if：如果 n u m s [ j ] > k e y nums[j]>key nums[j]>key，那么我们就要继续向前比较，但是考虑到我们最后插入 k e y key key的时候，还要对数组向后移动，我们就另 n u m s [ j + 1 ] = n u m s [ j ]   然 后   j − − nums[j+1]=nums[j]~然后~j-- nums[j+1]=nums[j] 然后 j−−，直到 n u m s [ j ] ≤ k e y   ∣ ∣   j = = 0 nums[j] leq key~||~j==0 nums[j]≤key ∣∣ j==0，这个时候停止遍历。

代码：

在代码中，我们使用Java的内置方法：System.currentTimeMillis，在后面的文章中，我们会使用不同的方法来计算运行时间，有兴趣的可以继续关注哦。

package com.company;
import java.util.*;

public class Main {
    public static int[] nums;//定义数组
    public static int size;//定义数组大小

    public static void insertionSort(){
        for(int i = 1; i < size; i++){
            int key = nums[i];
            int j = i-1;
            while(j >= 0 && nums[j] > key){ //注意这里的 j>=0 必须要在 && 的前面，否则会由于 index=-1 越界报错
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = key; // j 在前面的while循环中最后多减了一次，所以这里用 j+1
        }
    }
    public static void createArray(){ //生成随机数组：
        Random rand = new Random();
        for(int i = 0; i < size; i++)
            nums[i] = rand.nextInt(1000);
    }
    public static void printArray(){
        int step = 30;
        for(int i = 0; i < size; i++) {
            if(i == step){
                System.out.println();
                step += 20;
            }
            System.out.print(nums[i] + " ");
        }
    }
    public static void main(String[] args) {
	// write your code here
        Scanner in = new Scanner(System.in);
        System.out.print("输入数组的大小：");
        size = in.nextInt();//输入数组的大小
        nums = new int[size];
        //创造数组
        createArray();
        System.out.println("排序前的数组为：");
        printArray();
        //开始排序
        //开始
        double start_time = System.currentTimeMillis();
        insertionSort();
        //结束
        double end_time = System.currentTimeMillis();
        double time =end_time - start_time;

        System.out.println('n' + "排序后的数组为：");
        printArray();
        System.out.println('n' + "运行时间为：" + time + "毫秒");
        in.close();
    }
}

输入示例：

由于数组大小比较小，下面我们分别记录： s i z e = [ 1000 5000 10000 50000 100000 500000 1000000 5000000 10000000 50000000 100000000 500000000 1000000000 5000000000 ] size=begin{bmatrix}1000&5000&10000&50000&100000&500000&1000000\5000000&10000000&50000000&100000000&500000000&1000000000&5000000000end{bmatrix} size=[10005000000​500010000000​1000050000000​50000100000000​100000500000000​5000001000000000​10000005000000000​]

代码结果为：（由于运行时间过长，就没有全部展示）

看关键的代码部分（伪代码）：
f o r   j = 2   t o   A . l e n g t h for ~ j=2~to~A.length for j=2 to A.length
k e y = A [ i ] quad key=A[i] key=A[i]
i = j − 1 quad i=j-1 i=j−1
w h i l e   i > 0   & &   A [ i ] > k e y quad while~i>0~&&~A[i]>key while i>0 && A[i]>key
A [ i + 1 ] = A [ i ] qquad A[i+1]=A[i] A[i+1]=A[i]
i = i − 1 qquad i=i-1 i=i−1
A [ i + 1 ] = k e y quad A[i+1]=key A[i+1]=key

最好情况为：数组已经排好序。那么 w h i l e while while 语句就只执行了 n n n 次，那么最后的时间复杂度就是： O ( n ) pmb{O(n)} O(n)​O(n)​​O(n)最坏情况为：数组为倒序，那么 w h i l e 循 环 语 句 加 上 其 内 部 就 一 共 执 行 了 ： ∑ j = 2 n ( j )   次 while循环语句加上其内部就一共执行了：sumlimits_{j=2}^{n}(j)~次 while循环语句加上其内部就一共执行了：j=2∑n​(j) 次，这样，时间复杂度就是 O ( n 2 ) pmb{O(n^2)} O(n2)​O(n2)​​O(n2)平均情况就是： O ( n 2 ) pmb{O(n^2)} O(n2)​O(n2)​​O(n2)