排序算法之选择和插入排序！

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素。

然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

由于存在数据交换，选择排序不是稳定的排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class SelectionSort {
    public int[] selectionSort(int[] A, int n) {
        //记录最小下标值
        int min=0;
        for(int i=0; i<A.length-1;i++){
            min = i;
            //找到下标i开始后面的最小值
            for(int j=i+1;j<A.length;j++){
                 if(A[min]>A[j]){
                     min = j;
                 }
            }
            if(i!=min){
                swap(A,i,min);
            }
        }
        return A;
    }
    private void swap(int[] A,int i,int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class InsertionSort {
    public int[] insertionSort(int[] A, int n) {
      //用模拟插入扑克牌的思想
        //插入的扑克牌
        int i,j,temp;
        //已经插入一张，继续插入
        for(i=1;i<n;i++){
            temp = A[i];
            //把i前面所有大于要插入的牌的牌往后移一位，空出一位给新的牌
            for(j=i;j>0&&A[j-1]>temp;j--){
                A[j] = A[j-1];
            }
            //把空出来的一位填满插入的牌
            A[j] = temp;
        }
        return A;
    }
}