這兩種排序, 一種搜索方法是都會(huì)去使用的通用算法, 這三種方法簡(jiǎn)單而有效, 所以我把這三種方法記錄于此, 以便溫故知新, 因?yàn)樽罱谧屑?xì)研究JAVA, 所以此篇代碼都是以JAVA語(yǔ)言所寫(xiě).
同時(shí)也對(duì)知識(shí)進(jìn)行一下分享, 以方便大眾.
冒泡排序
這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，所以大家就把這個(gè)排序的算法命名為冒泡排序, 這種排序方法的優(yōu)點(diǎn)是有極佳的穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會(huì)再無(wú)聊地把他們倆交換一下的；如果兩個(gè)相等的元素沒(méi)有相鄰，那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換，所以相同元素的前后順序并沒(méi)有改變，所以冒泡排序是一種穩(wěn)定排序算法。
這種算法因?yàn)槠浜?jiǎn)單容易使用和穩(wěn)定性較好, 成為了剛剛接觸算法最好的入門算法之一.
綜合上文可以知曉可見(jiàn)冒泡排序其核心思想就是經(jīng)過(guò)相鄰的兩個(gè)元素之間的比較交換位置來(lái)進(jìn)行排序的.
冒泡排序顯而易見(jiàn)我們需要用到判斷, 來(lái)判斷數(shù)組中相鄰兩個(gè)元素的值
而兩個(gè)元素之間的交換我們最常用的代碼就是
if (arr1[j] > arr[j + 1]){
// 非常簡(jiǎn)單基礎(chǔ)的交換瓶子中的水
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
而其中的 j 則代表了數(shù)組元素的下標(biāo)
光是這樣我們只能判斷一次相鄰數(shù)組的下標(biāo), 所以, 我們要讓他"動(dòng)"起來(lái), 顯而易見(jiàn)的, 我們需要用到for循環(huán)來(lái)聯(lián)動(dòng) j 的值
for (int j = 0; j < arr.length - 1 - i; j++){
if (arr[j] > arr[j + 1]){
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
這個(gè)for的循環(huán)就可以讓我們進(jìn)行一次整體的排序了, 但是明顯一次排序是不夠的, 比如 4, 2 ,1 這種情況, 一次整體排序完成也只是變成 2, 1, 4 而且, 一次整體的排序只能夠讓一個(gè)最大的值"浮"上來(lái), 但我們需要不斷地讓下一個(gè)最大值浮上來(lái), 所以我們需要多次的排序
重點(diǎn)來(lái)了
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]){
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
每一次外圈的循環(huán)都會(huì)使一個(gè)最大值"浮"上來(lái), 很明顯的, 外圈的循環(huán)次數(shù)就是數(shù)組元素的個(gè)數(shù), 而內(nèi)圈的 arr.length - 1 - i 則是每一次外圈循環(huán)之后就有一個(gè)最大值"浮動(dòng)"上來(lái), 最后的值就不用再去檢驗(yàn)了, 所以就是 - i.
最常用的一種冒泡排序的兩種不同寫(xiě)法
數(shù)組為
int[] arr = {4, 2, 1, 5, 3, 7, 10, 9};
第一種, 也是講解的一種
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]){
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
第二種
for (int i = arr.length - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j + 1] < arr[j])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
兩種代碼運(yùn)行之后的結(jié)果是
// 遍歷并打印數(shù)組中的值
for (int i:arr
) {
System.out.println(i);
}
選擇排序
冒泡排序這么仔細(xì)就是要為選擇排序打底
for (int i = 0; i < arr.length - 1; i++){
for (int j = i + 1; j < arr.length; j++){
if (arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
而這個(gè)就是選擇排序
它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
以一次循環(huán)為例子, 冒泡循環(huán)是一直兩個(gè)兩個(gè)相鄰的比較排序, 而選擇排序則是, 拿一個(gè)跟所有的待選擇的數(shù)據(jù)比較而進(jìn)行排序
折半查找
這個(gè)方法就是二分法, 在生活當(dāng)中其實(shí)也經(jīng)常會(huì)用到, 很常見(jiàn)的, 在 1 到 100 當(dāng)中想一個(gè)數(shù), 我會(huì)問(wèn)你50大于小于你想的數(shù), 你說(shuō)50小于你想的數(shù), OK, 那75是不是你想的數(shù)字大了還是小了? 你說(shuō)小了, 那87是不是, 大了, 93呢........
這個(gè)方法通過(guò)不斷的對(duì)一個(gè)數(shù)組取中間數(shù), 來(lái)判斷這個(gè)數(shù)字到底是多少
上代碼
int seach(int[] arr, int key){
// 折半查找(二分法)
// 前提: 有序的數(shù)據(jù)
// 有點(diǎn): 效率高是個(gè)數(shù)組元素多的查找
int min, max, mid;
min = 0;
max = arr.length - 1;
while (min <= max){
mid = (min + max) / 2;
if (arr[mid] < key){
min = mid + 1;
} else if (arr[mid] > key){
max = mid - 1;
} else {
System.out.println(mid);
return mid;
// break;
}
}
return -1;
}
這個(gè)代碼是用來(lái)查找數(shù)組中與key值相同值的下標(biāo)
我們?cè)谑褂玫臅r(shí)候, 一般需要一個(gè)數(shù)組和一個(gè)key值, 這個(gè)key值就是你想要找出來(lái)的數(shù)字, 通過(guò)while去循環(huán), mid就是不斷被取中間值的下標(biāo), 中間值大于key則 最大值一定就是mid - 1 , mid < key 同理, 而一旦arr[mid] == key 則key值你就找到了.
