一、冒泡排序
冒泡排序是一種簡單的排序算法绩蜻。它重復地走訪過要排序的數(shù)列铣墨，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來辜羊。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換踏兜，也就是說該數(shù)列已經(jīng)排序完成词顾。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端八秃。
//1.冒泡排序
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
二、快速排序
快速排序的基本思想：
通過一趟排序將待排序記錄分割成獨立的兩部分肉盹，其中一部分記錄的關鍵字均比另一部分關鍵字小昔驱，則分別對這兩部分繼續(xù)進行排序，直到整個序列有序上忍。
把整個序列看做一個數(shù)組骤肛，把第零個位置看做中軸，和最后一個比窍蓝，如果比它小交換腋颠，比它大不做任何處理；交換了以后再和小的那端比吓笙，比它小不交換淑玫，比他大交換。這樣循環(huán)往復，一趟排序完成絮蒿，左邊就是比中軸小的尊搬，右邊就是比中軸大的，然后再用分治法土涝，分別對這兩個獨立的數(shù)組進行排序佛寿。
//2、快速排序
/**
* @param arr 待排序列
* @param leftIndex 待排序列起始位置
* @param rightIndex 待排序列結束位置
*/
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
}
//從左開始的起點
int left = leftIndex;
//從右開始的起點
int right = rightIndex;
//默認左側第一個元素為基準值
int key = arr[left];
//從兩頭開始交替掃描但壮，知道left=right
while (left < right) {
//先從右邊開始掃描
while (left < right && arr[right] >= key) {
right--;
}
//交換位置 把右邊<key的值移到左邊
arr[left] = arr[right];
//然后從左向右開始掃描
while (left < right && arr[left] <= key) {
left++;
}
//交換位置 把左邊>key的值移到右邊
arr[right] = arr[left];
}
//基準值歸位
arr[left] = key;
//對基準值左側的數(shù)組進行排序
quickSort(arr, leftIndex, left - 1);
//對基準值右側的數(shù)組進行排序
quickSort(arr, right + 1, rightIndex);
}
三冀泻、選擇排序
基本思想：在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換蜡饵；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換腔长，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。
//3 選擇排序
public static void selectSort(int[] arr) {
int size = arr.length;
int temp;
int minIndex;
for (int i = 0; i < size - 1; i++) {
minIndex = i;//暫定第i個元素的位置
//找出i以后最小值验残，就是i位置上應該擺放的值捞附。 其索引即是 minIndex
for (int j = i + 1; j < size; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
//交換兩個元素
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
四、插入排序
1您没、基本思想：在要排序的一組數(shù)中鸟召，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換氨鹏，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止欧募。
//4、插入排序
public static void insertSort(int[] arr) {
int size = arr.length;
int temp;
int j;
for (int i = 1; i < size; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
五仆抵、希爾排序
希爾排序的原理:根據(jù)需求跟继，如果你想要結果從大到小排列，它會首先將數(shù)組進行分組镣丑，然后將較大值移到前面舔糖，較小值移到后面，最后將整個數(shù)組進行插入排序莺匠，這樣比起一開始就用插入排序減少了數(shù)據(jù)交換和移動的次數(shù)金吗，可以說希爾排序是加強版的插入排序
- 拿數(shù)組5, 2, 8, 9, 1, 3，4來說趣竣，數(shù)組長度為7摇庙，當increment為3時，數(shù)組分為兩個序列
- 5遥缕，2卫袒，8和9，1单匣，3夕凝，4烤蜕，第一次排序，9和5比較迹冤，1和2比較讽营，3和8比較，4和比其下標值小increment的數(shù)組值相比較
- 此例子是按照從大到小排列泡徙，所以大的會排在前面橱鹏，第一次排序后數(shù)組為9, 2, 8, 5, 1, 3，4
- 第一次后increment的值變?yōu)?/2=1,此時對數(shù)組進行插入排序堪藐，
*實現(xiàn)數(shù)組從大到小排
//5莉兰、希爾排序
public static void shellSort(int[] arr) {
int size = arr.length;
int j;
int temp;
for (int increment = size / 2; increment > 0; increment /= 2) {
for (int i = increment; i < size; i++) {
temp = arr[i];
for (j = i; j >= increment; j -= increment) {
if (temp < arr[j - increment]) {
arr[j] = arr[j - increment];
} else {
break;
}
}
arr[j] = temp;
}
}
}
六、歸并排序
基本思想：
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表礁竞，即把待排序序列分為若干個子序列糖荒，每個子序列是有序的。然后再把有序子序列合并為整體有序序列模捂。
//6捶朵、歸并排序
public static int[] sort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
sort(arr, low, mid);
sort(arr, mid + 1, high);
merge(arr, low, high);
}
return arr;
}
public static void merge(int[] arr, int low, int high) {
int[] temp = new int[high - low + 1];
int mid = (low + high) / 2;
int i = low;//左數(shù)組 指針
int j = mid + 1;//右數(shù)組 指針
int k = 0;//數(shù)組temp的指針
while (i <= mid && j <= high) {//左右兩個數(shù)組，至少有一個會先加完即i>mid或j>high狂男，而退出循環(huán)
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
//①综看，②以下兩個循環(huán)只會進入一個
//①把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = arr[i++];
}
//②把右邊剩余的數(shù)移入數(shù)組
while (j <= high) {
temp[k++] = arr[j++];
}
//把臨時數(shù)組覆蓋到原數(shù)組
for (int i1 = 0; i1 < temp.length; i1++) {
arr[i1 + low] = temp[i1];
}
}
