冒泡排序
對(duì)于一個(gè)數(shù)組來說狈惫，每次相鄰兩個(gè)元素進(jìn)行比較筷凤，如果第二個(gè)元素小于第一個(gè)元素就進(jìn)行交換（升序排序的情況），這樣子每次循環(huán)完畢后忙干，待排序數(shù)組里面最大的值都會(huì)移動(dòng)到末尾，下次循環(huán)就可以不用考慮判斷末尾的情況了浪藻。
時(shí)間復(fù)雜度：O（n方）
public void bubbleSort(int[] q) {
for(int i = 1; i < q.length; i++) {
for(int j = 0; j < q.length - i; j++) {
if(q[j] > q[j + 1]) {
int temp = q[j];
q[j] = q[j + 1];
q[j + 1] = temp;
}
}
}
}
選擇排序
在第i次循環(huán)中捐迫，每次從待排序的數(shù)組中選擇一個(gè)最小的元素，放到第i個(gè)位置爱葵。那么循環(huán)結(jié)束后就可以得到一個(gè)升序數(shù)組了
時(shí)間復(fù)雜度：O（n方）
public static void selectSort(int[] q) {
for(int i = 0; i < q.length - 1; i++) {
int min = i;
for(int j = i + 1; j < q.length; j++) {
if(q[j] < q[min]) {
min = j;
}
}
if(i != min) {
int temp = q[i];
q[i] = q[min];
q[min] = temp;
}
}
}
插入排序
每次循環(huán)施戴，前i個(gè)位置構(gòu)成的數(shù)組都是有序的數(shù)組，即每次都會(huì)把新的元素與他之前的元素進(jìn)行比較萌丈，如果新元素小就互換位置赞哗，while循環(huán)會(huì)一直換直到新元素到了該到的位置，這樣子新的數(shù)組又是一個(gè)有序數(shù)組辆雾，然后在去把下一個(gè)元素插入進(jìn)來肪笋。雖然名字是插入排序，但是因?yàn)槊看味家c前面一個(gè)進(jìn)行比較再互換度迂，所以還是穩(wěn)定的排序藤乙。
時(shí)間復(fù)雜度：O（n方）
public void insertSort(int[] q) {
for(int i = 1; i < q.length; i++) {
int j = i;
while(q[j] < q[j - 1] && j > 0) {
int temp = q[j];
q[j] = q[j - 1];
q[j - 1] = temp;
j --;
}
}
}
歸并排序
分治法是把一個(gè)問題分成n個(gè)子問題去看待。要對(duì)一個(gè)數(shù)組排序惭墓，可以把它分成兩個(gè)同等規(guī)模的數(shù)組坛梁，這兩個(gè)數(shù)組分別排序完后再合并成一個(gè)有序數(shù)組，而兩個(gè)數(shù)組可以分為四個(gè)同等規(guī)模的數(shù)組腊凶，一直分到最后一個(gè)數(shù)組只有兩個(gè)元素划咐。合并的過程就是申請(qǐng)一個(gè)新數(shù)組毅人，然后雙指針，哪個(gè)數(shù)組指向的小就放到新數(shù)組中尖殃，最后有個(gè)數(shù)組會(huì)有剩下來的值丈莺，直接放到新數(shù)組的末尾。
public void merge(int []q, int l, int r) {
if(l >= r) return;
int mid = ((r - l) >> 1) + l;
merge(q, l, mid);
merge(q, mid + 1, r);
int k = 0;
int i = l;
int j = mid + 1;
int []temp = new int[q.length];
while(i <= mid && j <= r) {
if(q[i] <= q[j]) {
temp[k ++ ] = q[i ++ ];
}else {
temp[k ++ ] = q[j ++ ];
}
}
while(i <= mid) temp[k ++ ] = q[i ++ ];
while(j <= r) temp[k ++ ] = q[j ++ ];
for(i = l, j = 0; i <= r; i++, j++) {
q[i] = temp[j];
}
}
快速排序
選擇一個(gè)最中間的元素當(dāng)做基準(zhǔn)送丰，然后雙指針指向頭和尾缔俄，如果頭指針的元素小于中間值就繼續(xù)往后移動(dòng)，如果尾指針的元素大于中間值就往前移動(dòng)器躏，當(dāng)他們兩個(gè)都停下來的時(shí)候俐载，如果頭指針小于尾指針的位置，那么就交換兩個(gè)位置的元素登失，然后一直循環(huán)直到頭指針大于等于尾指針的位置遏佣。一次快排就結(jié)束了，這個(gè)時(shí)候j這個(gè)位置左邊的元素都比他小揽浙，右邊的元素都比他大状婶，分別進(jìn)行兩次快排。
時(shí)間復(fù)雜度：O（nlogn）馅巷，正常情況下快排的速度比歸并還快膛虫，但是快排也是一種不穩(wěn)定的排序，不穩(wěn)定的排序一般有四種钓猬，快希選堆（快速排序稍刀，希爾排序，選擇排序敞曹，堆排序）
public void quickSort(int[] q, int l, int r) {
if(l >= r)
return;
int i = l - 1;
int j = r + 1;
int x = q[l + r >> 1];
while(i < j) {
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
