冒泡排序
算法規(guī)則： 由于算法每次都將一個(gè)最大的元素往上冒奶镶，我們可以將待排序集合(0...n)看成兩部分，一部分為(k..n)的待排序unsorted集合，另一部分為(0...k)的已排序sorted集合，每一次都在unsorted集合從前往后遍歷傅是，選出一個(gè)數(shù)，如果這個(gè)數(shù)比其后面的數(shù)大威创，則進(jìn)行交換落午。完成一輪之后，就肯定能將這一輪unsorted集合中最大的數(shù)移動(dòng)到集合的最后肚豺，并且將這個(gè)數(shù)從unsorted中刪除，移入sorted中界拦。冒泡排序的時(shí)間復(fù)雜度為O(n^2)吸申。
代碼實(shí)現(xiàn)(java)
public void bubbleSort(int[] data){
//這里從數(shù)組最后面開始遍歷
for (int i = data.length - 1; i > 0; --i) {
//在這里體現(xiàn)出 “將每一趟排序選出來(lái)的最大的數(shù)從sorted中移除”
for (int j = 0; j < i; j++) {
//保證在相鄰的兩個(gè)數(shù)中比較選出最大的并且進(jìn)行交換(冒泡過(guò)程)
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
并歸排序
- 算法規(guī)則： 像快速排序一樣，由于歸并排序也是分治算法享甸，因此可使用分治思想：
1.申請(qǐng)空間截碴，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
2.設(shè)定兩個(gè)指針蛉威，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3.比較兩個(gè)指針?biāo)赶虻脑厝盏ぃx擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4.重復(fù)步驟3直到某一指針到達(dá)序列尾
5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾
空間復(fù)雜度為O(n)蚯嫌，時(shí)間復(fù)雜度為O(nlogn)哲虾。 - 代碼實(shí)現(xiàn)(java)
public void mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
//左邊
mergeSort(a, low, mid);
//右邊
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
private void merge(int[] a, 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 (a[i] > a[j]) {
temp[k++] = a[j++];
} else {
temp[k++] = a[i++];
}
}
//左邊剩余的數(shù)據(jù)加入得到新數(shù)組
while (i <= mid) {
temp[k++] = a[i++];
}
//右邊剩余的數(shù)據(jù)加入到新數(shù)組
while (j <= high) {
temp[k++] = a[j++];
}
for (int l = 0; l < temp.length; l++) {
a[l + low] = temp[l];
}
}
快速排序
算法規(guī)則： 本質(zhì)來(lái)說(shuō)，快速排序的過(guò)程就是不斷地將無(wú)序元素集遞歸分割择示，一直到所有的分區(qū)只包含一個(gè)元素為止束凑。
由于快速排序是一種分治算法，我們可以用分治思想將快排分為三個(gè)步驟：
1.分：設(shè)定一個(gè)分割值栅盲，并根據(jù)它將數(shù)據(jù)分為兩部分
2.治：分別在兩部分用遞歸的方式汪诉，繼續(xù)使用快速排序法
3.合：對(duì)分割的部分排序直到完成
快速排序是不穩(wěn)定的，其時(shí)間平均時(shí)間復(fù)雜度是O(nlgn)谈秫。代碼實(shí)現(xiàn)(java)
public static int dividerAndChange(int[] args, int start, int end) {
//參照值
int pivot = args[start];
while (start < end) {
//首先從右向左查找,直到找到比參數(shù)小的第一個(gè)數(shù),然后交換位置
while (start < end && pivot <= args[end]) {
end--;
}
if (start < end) {
//開始交換位置
args[start] = args[end];
start++;
}
//從左往右找扒寄，找到比參數(shù)大的就交換位置
while (start < end && pivot > args[start]) {
start++;
}
if (start < end) {
//開始交換位置
args[end] = args[start];
end--;
}
}
args[start] = pivot;
System.out.println("start:" + start + ",end:" + end);
return start;
}
public static void quickSort(int[] args, int start, int end) {
if (end - start > 1) {
int mid = dividerAndChange(args, start, end);
//對(duì)左邊數(shù)組排序
quickSort(args, start, mid);
//對(duì)右邊數(shù)組排序
quickSort(args, mid + 1, end);
}
}
選擇排序
算法規(guī)則： 將待排序集合(0...n)看成兩部分，在起始狀態(tài)中拟烫，一部分為(k..n)的待排序unsorted集合该编，另一部分為(0...k)的已排序sorted集合,在待排序集合中挑選出最小元素并且記錄下標(biāo)i，若該下標(biāo)不等于k构灸，那么 unsorted[i] 與 sorted[k]交換 上渴，一直重復(fù)這個(gè)過(guò)程岸梨，直到unsorted集合中元素為空為止写穴。選擇排序的時(shí)間復(fù)雜度為O(n^2)
代碼實(shí)現(xiàn)(java)
public void selectionSort(int[] args){
for (int i = 0; i < args.length - 1; i++) {
int k = i;
for (int j = k + 1; j < args.length; j++) {
//循環(huán)遍歷,找到最小值的下標(biāo)
if (args[j] < args[k]) {
k = j;
}
}
if (k != i) {
//交換args[i]和args[k]
int temp = args[i];
args[i] = args[k];
args[k] = temp;
}
}
}
插入排序
- 算法規(guī)則：插入排序不是通過(guò)交換位置而是通過(guò)比較找到合適的位置插入元素來(lái)達(dá)到排序的目的的寻歧。相信大家都有過(guò)打撲克牌的經(jīng)歷，特別是牌數(shù)較大的鉴未。在分牌時(shí)可能要整理自己的牌隔披，牌多的時(shí)候怎么整理呢赃份？就是拿到一張牌，找到一個(gè)合適的位置插入奢米。這個(gè)原理其實(shí)和插入排序是一樣的抓韩。舉個(gè)栗子，對(duì)5,3,8,6,4這個(gè)無(wú)序序列進(jìn)行簡(jiǎn)單插入排序鬓长，首先假設(shè)第一個(gè)數(shù)的位置時(shí)正確的谒拴，想一下在拿到第一張牌的時(shí)候，沒(méi)必要整理涉波。然后3要插到5前面英上，把5后移一位，變成3,5,8,6,4.想一下整理牌的時(shí)候應(yīng)該也是這樣吧啤覆。然后8不用動(dòng)苍日，6插在8前面，8后移一位窗声，4插在5前面相恃，從5開始都向后移一位。注意在插入一個(gè)數(shù)的時(shí)候要保證這個(gè)數(shù)前面的數(shù)已經(jīng)有序笨觅。簡(jiǎn)單插入排序的時(shí)間復(fù)雜度也是O(n^2)拦耐。
/**
* 插入排序
* @param args
* @return
*/
public static int[] insertSort(int[] args) {
if (args.length == 0) {
return null;
}
// 默認(rèn)數(shù)組的第一個(gè)數(shù)字已經(jīng)排好序
// 這里把第二個(gè)數(shù)字,作為拿來(lái)比較的數(shù)字.假設(shè)第一個(gè)數(shù)字位置已經(jīng)確定.然后將二個(gè)數(shù)字和第一個(gè)數(shù)字比較
for (int i = 1; i < args.length; i++) {
int k = i;
//這里將未排序的第一個(gè)數(shù)字拿出來(lái)
int target = args[i];
/*for (k = i - 1; k >= 0 && target < args[k]; k--) {
args[k + 1] = args[k];
}*/
//這里循環(huán)比較,將未排序的第一個(gè)數(shù)和前面已排序的數(shù)組循環(huán)比較
while (k >= 0 && target < args[k - 1]) {
args[k] = args[k - 1];
k--;
}
//這里重新設(shè)置參照值.
args[k] = target;
}
return args;
}
