1.算法介紹
1.1 選擇排序
選擇排序的工作原理在于每一次從待排序的數(shù)據(jù)元素中選出最邪曷摹(或最大)的一個元素寂诱,存放在序列的起始位置拂苹,直到全部待排序的數(shù)據(jù)元素排完痰洒。
代碼實現(xiàn)如下:
public static void selectionSort(int[] arr){
for(int i = 0; i < arr.length - 1; i++){
int min = i;
for(int j = i + 1; j < arr.length; j++)
if(arr[j] < arr[min])
min = j;
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
1.2 冒泡排序
比較相鄰的元素,如果第一個元素比第二個元素大的話就交換位置丘喻,對每一對相鄰元素都進行這樣的操作,那么最后的元素就是最大的元素泉粉。然后對前n - 1個元素進行同樣的操作连霉,直到?jīng)]有相鄰元素可以比較,那么排序就完成了跺撼。
代碼實現(xiàn)如下:
public static void bubbleSort(int[] arr){
for(int i = 0; i < arr.length - 1; i++){
for(int j = 0; j < arr.length - i - 1; j++){
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
1.3 插入排序
插入排序的基本思想是:每步將一個待排序的紀(jì)錄,按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上歉井,直到全部插入完為止。與選擇排序一樣哩至,當(dāng)前索引的左邊的所有元素是有序的,但它們的最終位置還不確定菩貌,為了給更小的元素騰出空間卢佣,可能需要被移動箭阶。和選擇排序不同的是虚茶,插入排序所需的時間取決于輸入元素的初始順序尾膊。
代碼實現(xiàn)如下:
public static void insertionSort(int[] arr){
for(int i = 1; i < arr.length; i++){
for(int j = i; j > 0 && arr[j - 1] > arr[j]; j--){
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
1.4 希爾排序
希爾排序是基于插入排序的排序算法,它的基本思想是先將整個待排記錄序列分割成若干個子序列冈敛,待整個序列中的記錄“基本有序”時待笑,再對全體記錄進行一次直接插入排序抓谴。而子序列的構(gòu)成不是簡單地“逐段分割”暮蹂,而是將相隔某個增量的記錄來組成一個子序列癌压。如何選取增量序列是決定希爾排序性能的重要因素,但至今尚未有人求得最佳的增量序列滩届。
代碼實現(xiàn)如下集侯,增量序列為 1/2(3^k - 1):
public static void shellSort(int[] arr){
int N = arr.length;
int h = 1;
while(h < N/3)
h = 3*h + 1;
while(h >= 1){
for(int i = h; i < N; i++){
for(int j = i; j >= h && arr[j - h] > arr[j]; j -= h){
int temp = arr[j];
arr[j] = arr[j - h];
arr[j - h] = temp;
}
}
h = h / 3;
}
}