1. Java排序：冒泡排序 - 最簡單
（1）比較前后相鄰的二個數(shù)據(jù)嫉髓，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將這二個數(shù)據(jù)交換邑闲。
（2）這樣對數(shù)組的第 0 個數(shù)據(jù)到 N-1 個數(shù)據(jù)進行一次遍歷后算行，最大的一個數(shù)據(jù)就“沉”到數(shù)組第N-1個位置。
（3）N=N-1苫耸，如果 N 不為 0 就重復前面二步州邢，否則排序完成。
【邏輯】外層0 ~ <length-1褪子，內(nèi)層0 ~ <length-1-i量淌。相鄰元素，比較大小嫌褪，互換位置
【優(yōu)點】穩(wěn)定
【缺點】慢呀枢，每次只能移動相鄰兩個數(shù)據(jù)
public class TestArraySort{
public static void main(String[] args) {
// Test 冒泡
int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
bubbleSort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
}
}
/**
* Java排序：冒泡排序
* 說明：相鄰元素，比較大小笼痛，互換位置
* @param array 需要排序的無序整數(shù)類型數(shù)組
*/
public static void bubbleSort(int[] array) {
// 1. 參數(shù)合法性判斷
if (null == array || array.length == 0) {
return;
}
// 2. 冒泡排序主邏輯
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1 - i; j++) {
if (array[j] > array[j+1]) { // 相鄰元素裙秋，升序
//if (array[j] < array[j+1]) { // 相鄰元素，降序
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
}
2. Java排序：插入排序 - 簡單
通過構建有序序列缨伊，對于未排序數(shù)據(jù)摘刑，在已排序序列中從后向前掃描，找到相應的位置并插入刻坊。
插入排序非常類似于整撲克牌枷恕。在開始摸牌時，左手是空的谭胚，牌面朝下放在桌上徐块。接著隶校，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上蛹锰。為了找到這張牌的正確位置深胳，要將它與手中已有的牌從右到左地進行比較。無論什么時候铜犬，左手中的牌都是排好序的舞终。
如果輸入數(shù)組已經(jīng)是排好序的話，插入排序出現(xiàn)最佳情況癣猾，其運行時間是輸入規(guī)模的一個線性函數(shù)敛劝。如果輸入數(shù)組是逆序排列的，將出現(xiàn)最壞情況纷宇。平均情況與最壞情況一樣夸盟，其時間代價是(n2)。
【邏輯】外層1 ~ <length像捶，內(nèi)層i ~ 0上陕。第2個數(shù)開始，與前面的數(shù)逐個比較拓春，插入位置
【優(yōu)點】穩(wěn)定释簿，快
【缺點】比較次數(shù)不一定，比較次數(shù)越少硼莽，插入點后的數(shù)據(jù)移動越多庶溶，特別是當數(shù)據(jù)總量龐大的時候
public class TestArraySort{
public static void main(String[] args) {
int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
insertSort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
}
}
/**
* Java排序：插入排序
* 說明：第2個數(shù)開始，與前面的數(shù)逐個比較懂鸵，插入位置
* @param array 需要排序的無序整數(shù)類型數(shù)組
*/
public static void insertSort(int[] array) {
// 1. 參數(shù)合法性判斷
if (null == array || array.length == 0) {
return;
}
// 2. 插入排序主邏輯
for (int i = 1; i < array.length; i++) { // 從第2個數(shù)temp開始
for (int j = i; j > 0; j--) { // temp每次與前面的數(shù)比較偏螺，插入進去
if (array[j] < array[j-1]) { // 升序
//if (array[j] < array[j-1]) { // 降序
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
}
}
3. Java排序：選擇排序 - 簡單
選擇排序（Selection sort）是一種簡單直觀的排序算法。
它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最写夜狻（或最大）的一個元素套像，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最信寡ā（大）元素凉夯，然后放到已排序的序列的末尾货葬。以此類推采幌，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。
選擇排序是不穩(wěn)定的排序方法震桶。
原因是用數(shù)組實現(xiàn)的選擇排序是不穩(wěn)定的休傍，用鏈表實現(xiàn)的選擇排序是穩(wěn)定的，因為數(shù)組內(nèi)會破壞相同元素的位置蹲姐，所以選擇排序是不穩(wěn)定的磨取。
在《算法》第四版217頁上作者已經(jīng)說了人柿，有很多辦法可以將任意排序算法變成穩(wěn)定的，但是忙厌，往往需要額外的時間或者空間凫岖。
【邏輯】外層0 ~ <length-1，i為固定值逢净，內(nèi)層i+1 ~ <length哥放。固定值與其他值依次比較，互換位置
【優(yōu)點】數(shù)據(jù)移動次數(shù)已知為（n-1）次
【缺點】比較次數(shù)多
public class TestArraySort {
public static void main(String[] args) {
int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
selectSort(nums);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
}
}
/**
* Java排序：選擇排序
* 說明：固定值與其他值依次比較爹土，互換位置
* @param array 需要排序的無序整數(shù)類型數(shù)組
*/
public static void selectSort(int[] array) {
// 1. 參數(shù)合法性判斷
if (null == array || array.length == 0) {
return;
}
// 2. 選擇排序主邏輯
for (int i = 0; i < array.length-1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) { // 升序：選擇1個數(shù)array[i]與i+1后面的數(shù)依次比較
//if (array[i] < array[j]) { // 降序
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
}
4. Java排序：快速排序 - 遞歸(難)
快速排序的原理：選擇一個關鍵值作為基準值甥雕。比基準值小的都在左邊序列（一般是無序的），比基準值大的都在右邊（一般是無序的）胀茵。一般選擇序列的第一個元素社露。
一次循環(huán)：從后往前比較，用基準值和最后一個值比較琼娘，如果比基準值小的交換位置峭弟，如果沒有繼續(xù)比較下一個，直到找到第一個比基準值小的值才交換脱拼。找到這個值之后孟害，又從前往后開始比較，如果有比基準值大的挪拟，交換位置挨务，如果沒有繼續(xù)比較下一個，直到找到第一個比基準值大的值才交換玉组。直到從前往后的比較索引 > 從后往前比較的索引谎柄，結束第一次循環(huán)，此時惯雳，對于基準值來說朝巫，左右兩邊就是有序的了。
【邏輯】選擇第一個數(shù)位基準值石景，開始首尾比較劈猿，首[0]基準值開始的i++找 ≤ 首值的進行交換，尾[length-1]基準值開始的j--找 ≥ 尾值的進行交換潮孽，找到中間后揪荣，兩半邊各自遞歸
【優(yōu)點】極快，數(shù)據(jù)移動少
【缺點】不穩(wěn)定（原因同選擇排序）
public class TestArraySort {
public static void main(String[] args) {
int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
quickSort(nums, 0, nums.length-1);
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
}
}
/**
* Java排序：快速排序
* 說明：選一個數(shù)作為基數(shù)(一般為array[0])往史，大于基數(shù)的放到右邊仗颈，小于這個基數(shù)的放到左邊
* @param array 需要排序的無序整數(shù)類型數(shù)組
* @param low 最小基準位置，eg：0
* @param high 最大基準位置椎例，eg：length-1
*/
public static void quickSort(int[] array, int low, int high) {
// 1. 參數(shù)合法性判斷
if (null == array || array.length == 0) {
return;
}
if (low > high) {
return;
}
// 2. 快速排序主邏輯
int i, j, temp, t;
i = low;
j = high;
temp = array[low]; // temp就是基準位
while (i < j) {
while (temp <= array[j] && i < j) { // 升序：先看右邊挨决，依次往左遞減
//while (temp >= array[j] && i < j) { // 降序：先看右邊请祖，依次往左遞遞增
j--;
}
while (temp >= array[i] && i < j) { // 升序：再看左邊，依次往右遞增
//while (temp <= array[i] && i < j) { // 降序：再看左邊脖祈，依次往右遞減少
i++;
}
if (i < j) { // 如果滿足條件則交換
t = array[j];
array[j] = array[i];
array[i] = t;
}
}
// 最后將基準為與i和j相等位置的數(shù)字交換
array[low] = array[i];
array[i] = temp;
quickSort(array, low, j - 1); // 遞歸調用左半邊數(shù)組
quickSort(array, j + 1, high); // 遞歸調用右半邊數(shù)組
}
}
5. Java算法：二分查找 - 升降序邏輯處理
又叫折半查找肆捕，要求待查找的序列有序。
默認升序邏輯說明：每次取中間位置的值與待查關鍵字比較盖高，如果中間位置的值比待查關鍵字大福压，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關鍵字小或舞，則在后半部分循環(huán)這個查找的過程荆姆。直到查找到了為止，否則序列中沒有待查的關鍵字映凳。
- 示例代碼：（嚴謹?shù)呐袛嗟ㄍ病⒂行?升,降序的處理）
public class TestBinarySearch {
public static void main(String[] args) {
int result = 0;
// Test 升序
int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
result = binarySearch(nums1, 3);
System.out.println(result); // 2
// Test 降序
int[] nums2 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
result = binarySearch(nums2, 3);
System.out.println(result); // 6
// Test 無序
int[] nums3 = {1, 8, 3, 6, 2, 9, 7, 4, 5};
result = binarySearch(nums3, 3);
System.out.println(result); // -1
}
/**
* Java算法：二分查找/折半查找
* 說明：默認有序，但需判斷知道其為升序還是降序
* @param array 被查找的數(shù)組诈豌，要求默認有序
* @param a 需要查找的數(shù)
* @return int 下標位置
*/
public static int binarySearch(int[] array, int a) {
// 1. 參數(shù)合法性判斷
if (null == array || array.length == 0) {
return -1;
}
// 2. 判斷是否有序仆救，以及升序 or 降序
boolean up = false;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] < array[i+1]) {
if (i+1 == array.length-1) { // 遍歷到最大下標才算
up = true; // 降序
}
} else if (array[i] > array[i + 1]) {
if (i+1 == array.length - 1) { // 遍歷到最大下標才算
up = false; // 升序
}
} else {
return -1;
}
}
// 3. 二分查找主邏輯循環(huán)
int minIndex = 0;
int maxIndex = array.length - 1;
int midIndex;
while (minIndex <= maxIndex) { // maxIndex/minIndex動態(tài)變化，折半遍歷
midIndex = (minIndex + maxIndex) / 2;
if (array[midIndex] > a) {
if (up) {
maxIndex = midIndex-1; // 升序左移
} else {
minIndex = midIndex+1; // 降序右移
}
} else if (array[midIndex] < a) {
if(up) {
minIndex = midIndex+1; // 升序右移
} else {
maxIndex = midIndex-1; // 降序左移
}
} else { // array[midIndex] == a
return midIndex;
}
}
return -1;
}
}
