排序算法
- 冒泡(Bubble)
- 選擇
- 插入
- 歸并
- 快速
- 計(jì)數(shù)排序
冒泡排序
簡(jiǎn)單的說(shuō)就是捐凭，每一次遍歷都把最大(小)的通過(guò)比較選出來(lái)养涮。
- 從第一個(gè)元素開(kāi)始比較相鄰的兩個(gè)元素治专，把大（腥彀）的往后移；
- 比較到未排序的最后一個(gè)元素時(shí)，會(huì)得出這趟冒泡得到的最大（卸懒睢）元素端朵；
- 一直遍歷到只有一個(gè)元素
代碼實(shí)現(xiàn)：
(java)
int []a = {5,4,3,2,1,12,32,13,24,53};
for (int i = a.length - 1 ; i >0; i--){
for (int j = 0;j< i;j++){
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
選擇排序
這個(gè)算法也很簡(jiǎn)單，每次都把未排序序列里最腥技（大）的選出來(lái)冲呢，放在序列。
- 一趟遍歷未排序序列招狸，選出最芯赐亍（大）的數(shù)字；
- 把這個(gè)數(shù)字放在未排序序列前面裙戏，*未排序序列 + 1
- 重復(fù)步驟到完成排序乘凸。
代碼實(shí)現(xiàn)：
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 0; i<a.length;i++){
int min = a[i];
int mark = i;
for(int j = i ;j <a.length ; j++){
if( min > a[j])
{
min = a[j];
mark = j;
}
}
int temp = a[i];
a[i] = min;
a[mark] = temp;
}
插入排序
排序流程：
- 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素累榜，在已經(jīng)排序的元素序列中從后向前掃描
- 如果被掃描的元素（已排序）大于新元素营勤，將該元素后移一位
- 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟 2~5
實(shí)現(xiàn)代碼：
package Sort;
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 1;i<a.length;i++){
int temp = a[i];
for (int j = i - 1 ; j>=0 ; j--){
if(temp < a[j]){
a[j+1] = a[j];
a[j] = temp;
}else{
break;
}
}
}
for (int i = 0 ; i< a.length ; i++)
System.out.print(a[i]+" ");
}
}
歸并排序
歸并排序采用呢壹罚，采用了分治法來(lái)讓兩個(gè)數(shù)組歸并葛作。
排序流程：
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和猖凛，該空間用來(lái)存放合并后的序列
- 設(shè)定兩個(gè)指針赂蠢，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間辨泳，并移動(dòng)指針到下一位置
- 重復(fù)步驟 3 直到某一指針到達(dá)序列尾
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左邊
sort(nums, low, mid);
// 右邊
sort(nums, mid + 1, high);
// 左右歸并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數(shù)先移到新數(shù)組中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右邊邊剩余的數(shù)移入數(shù)組
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
MergeSort.sort(a, 0, a.length-1);
for (int i = 0 ; i< a.length ; i++)
System.out.print(a[i]+" ");
}
