前言

??本文集將用java語言實(shí)現(xiàn)包括插入排序（直接插入、折半插入、希爾排序），交換排序（快速排序和冒泡排序），選擇排序，堆排序，歸并排序以及基數(shù)排序在內(nèi)的所有內(nèi)排序算法。雖然都很簡單且實(shí)際開發(fā)幾乎已運(yùn)用不到（Arrays.Sort和Collection.Sort可直接調(diào)用），但是這些屬于一個程序員的基本功，熟稔掌握是必須的。

算法

??直接插入排序的思想就是當(dāng)發(fā)現(xiàn)序列不是有序的情況下時，將待排序元素插入到前面已經(jīng)有序的序列中。所以怎么插是核心問題，其實(shí)歸根結(jié)底還是找到待排序元素的插入位置。由于是從小到大排序，可由待排序元素的前一個位置開始從后向前比較，若發(fā)現(xiàn)比較元素大于待排序元素，則將比較元素向后移位以騰出位置。最終將元素賦值給排序結(jié)束騰出的位置。
??邊比較邊移位是其特點(diǎn)，所以有待優(yōu)化的地方。后續(xù)的折半插入和希爾排序都是對直接插入排序的一種優(yōu)化。時間復(fù)雜度為o(n*n)。

例子

以序列 4 3 1 2 5為例

示例

Codes

package com.fairy.InnerSort;

import java.util.Scanner;

/**
 * 直接插入排序
 * @author Fairy2016
 *
 */
public class DirectInsertSort {
    
    public static void sort(int a[], int n) {
        int i,j;
        for(i = 2; i <= n; i++) {
            if(a[i-1] > a[i]) {
                a[0] = a[i];//a[0]作為探針，既存儲待排序元素又作循環(huán)停止標(biāo)志，省卻if判斷
                for(j = i-1; a[j] > a[0]; j--) {
                    a[j+1] = a[j];//遇到比a[i]大的向后移位，騰出位置
                }
                a[j+1] = a[0];//將待排序元素賦值到最終位置
            }
        }
    }
    
    public static void Print(int a[], int n) {
        for(int i = 1; i <= n; i++) {
            System.out.print(a[i]+" ");
        }
    }

    public static void main(String args[]) {
        int n;
        int a[];
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            n = scanner.nextInt();
            if(n > 0) {
                a = new int[n+1];
                for(int i=1; i <= n; i++) {
                    a[i] = scanner.nextInt();
                }
                sort(a, n);
                Print(a, n);
            }
        }
    }
}