概述
排序有内部排序和外部排序，内部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要通路外存。
我們這裡說說八大排序就是内部排序。
當n較大，則應采用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
快速排序：是目前基于比較的内部排序中被認為是最好的方法，當待排序的關鍵字是随機分布時，快速排序的平均時間最短；
1.插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
将一個記錄插入到已排序好的有序表中，進而得到一個新，記錄數增1的有序表。即：先将序列的第1個記錄看成是一個有序的子序列，然後從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。
直接插入排序示例：
如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。是以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序後的順序，是以插入排序是穩定的。
Java算法的實作：
public class InsertSort {
public void insertSort(int[] a) {
int i,j,temp;
for(i = 1; i < a.length; i++){
if(a[i] < a[i-1]){
temp = a[i];
for(j = i - 1; j >= 0 && a[j] > temp; j--){
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
for(i = 0;i < a.length; i++){
System.out.println(a[i]);
}
}
public static void main(String[] args) {
new InsertSort().insertSort(new int[]{9,1,5,8,3,7,4,6,2});
}
}
從空間上分析，直接插入排序算法隻需要一個輔助空間。
從時間複雜度上分析，最好的情況是排序的記錄本身是有序的，是以時間複雜度是 O(n)O(n) ；在最壞的情況，待排序的記錄是逆序的，那麼此時的時間複雜度是 O(n24)O(n24) 。是以雖然量級仍然是 n2
n2，但是直接插入排序算法的時間複雜度是優于冒泡排序算法和簡單選擇排序的。
2. 交換排序—冒泡排序（Bubble Sort）
基本思想：
在要排序的一組數中，對目前還未排好序的範圍内的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較後發現它們的排序與排序要求相反時，就将它們互換。
冒泡排序的示例：
算法的實作：
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j] > array[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
3. 選擇排序—簡單選擇排序（Simple Selection Sort）
基本思想：
在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然後在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最後一個數）比較為止。
簡單選擇排序的示例：
操作方法：
第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；
第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；
以此類推.....
第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第i 個記錄交換，
直到整個序列按關鍵碼有序。
算法實作：
public class SelectSort {
public void selectSort(int[] a){
int i,j,min;
for (i = 0; i < a.length; i++) {
//假設第一個位置的值是最小值
min = i;
for(j = i + 1; j < a.length; j++){
if(a[min] > a[j]){
min = j;
}
}
//如果min不等于i，說明找到最小值的下标
if(min != i){
swap(a,i,min);
}
}
for(i = 0; i < a.length; i++){
System.out.println(a[i]);
}
}
private void swap(int[] a, int i, int min) {
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
public static void main(String[] args) {
new SelectSort().selectSort(new int[]{9,1,5,8,3,7,4,6,2});
}
}