1.冒泡排序
依次比較相鄰的2個數,大的就往後排,第一輪下面就将最大的數放到了最後,
第2次就得到第2大的數,由于最後一個數不需要排序,那麼隻需要拍數組長度減1就全部排序完.
public class BubbleSort {
public static void BubbleSort(int[] arr) {
int temp;//定義一個臨時變量
for(int i=0;i<arr.length-1;i++){//冒泡趟數
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[]{1,42,34,12,5};
arr = bubbleSort(arr);
for (int i : arr) {
System.out.println(":"+i);
}
}
}
2.選擇排序
a) 原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最後，直到全部記錄排序完畢。也就是：每一趟在n-i+1(i=1，2，…n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基于此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。（這裡隻介紹常用的簡單選擇排序）
b) 簡單選擇排序的基本思想：給定數組：int[] arr={裡面n個資料}；第1趟排序，在待排序資料arr[1]arr[n]中選出最小的資料，将它與arrr[1]交換；第2趟，在待排序資料arr[2]arr[n]中選出最小的資料，将它與r[2]交換；以此類推，第i趟在待排序資料arr[i]~arr[n]中選出最小的資料，将它與r[i]交換，直到全部排序完成。
舉例：數組 int[] arr={5,2,8,4,9,1};
第一趟排序： 原始資料：5 2 8 4 9 1
最小資料1，把1放在首位，也就是1和5互換位置，
排序結果：1 2 8 4 9 5
第二趟排序：
第1以外的資料{2 8 4 9 5}進行比較，2最小，
排序結果：1 2 8 4 9 5
第三趟排序：
除1、2以外的資料{8 4 9 5}進行比較，4最小，8和4交換
排序結果：1 2 4 8 9 5
第四趟排序：
除第1、2、4以外的其他資料{8 9 5}進行比較，5最小，8和5交換
排序結果：1 2 4 5 9 8
第五趟排序：
除第1、2、4、5以外的其他資料{9 8}進行比較，8最小，8和9交換
排序結果：1 2 4 5 8 9
代碼:
public class SelectSort {
private static int[] selectSort(int[] arr){
for(int i=0;i<arr.length;i++){
int k = i; //記錄找出那個最小的數下标,0表示經過第一輪找出最小的放在arr[0],依此類推
for(int j=k+1;j<arr.length;j++){
if(arr[k]>arr[j]){
k = j; //依次和後面的數進行比較找出小的記住下标
}
//将找到的數放入指定位置
int t = arr[i];
arr[i] = arr[k];
arr[k] = t;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = new int[]{1,42,34,12,5};
int[] sort = selectSort(arr);
for (int i : sort) {
System.out.println(":"+i);
}
}
}
3.快速排序
原理,通過一趟掃描将要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一部分的所有資料都要小,然後再按此方法對這兩部分資料分别進行快速排序,整個排序過程可以遞歸進行,以此達到整個資料變成有序序列
舉個例子
如無序數組[6 2 4 1 5 9]
a),先把第一項[6]取出來,
用[6]依次與其餘項進行比較,
如果比[6]小就放[6]前邊,2 4 1 5都比[6]小,是以全部放到[6]前邊
如果比[6]大就放[6]後邊,9比[6]大,放到[6]後邊,//6出列後大喝一聲,比我小的站前邊,比我大的站後邊.
一趟排完後變成下邊這樣:
排序前 6 2 4 1 5 9
排序後 2 4 1 5 6 9
b),對前半拉[2 4 1 5]繼續進行快速排序
重複步驟a)後變成下邊這樣:
排序前 2 4 1 5
排序後 1 2 4 5
前半拉排序完成,總的排序也完成:
排序前:[6 2 4 1 5 9]
排序後:[1 2 4 5 6 9]
排序結束
public static void quickSort(int[] numbers, int start, int end) {
if (start < end) {
int base = numbers[start]; // 標明的基準值（第一個數值作為基準值）
int temp; // 記錄臨時中間值
int i = start, j = end;
do {
while ((numbers[i] < base) && (i < end))
i++;
while ((numbers[j] > base) && (j > start))
j--;
if (i <= j) {
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j)
quickSort(numbers, start, j);
if (end > i)
quickSort(numbers, i, end);
}
}
4.插入排序
從數組的第二個元素開始,将數組中的每一個元素按照（升序或者降序）規則插入到已排好序的數組中以達到排序的目的.
一般情況下将數組的第一個元素作為起始元素,從第二個元素開始依次插入。由于要插入到的數組是已經排好序的,是以隻要從右向左（或者從後向前）找到排序插入點插入元素，以此類推，直到将最後一個數組元素插入到數組中,整個排序過程完成。
每次将數組最後一個元素作為插入元素，與它前面有序（已排好序）的數組元素進行比較後，插入正确的位置，排序完成。（如下圖）
代碼:
/**
* 插入排序:
* 原理：每次将數組最後一個元素作為插入元素，與它前面有序（已排好序）的數組元素進行比較後，插入正确的位置，排序完成。
* 升序為例
*/
private static int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {// i: 代表即将插入的元素角标,作為每一組比較資料的最後一個元素
for (int j = i; j > 0; j--) { //j:代表數組角标
if (arr[j] < arr[j - 1]) {//符合條件，插入元素（交換位置）
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
return arr;
}
![九、設計模式以及查找、排序算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)