選擇排序
- 算法步驟
首先在未排序序列中找到最欣吧小（大）元素秦踪，存放到排序序列的起始位置捌肴。
再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最惺浇谩（大）元素狸驳，然后放到已排序序列的末尾预明。
重復(fù)第二步，直到所有元素均排序完畢耙箍。
-
動(dòng)圖演示
image
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class selectionSort {
public static void main(String[] args) {
List<Integer> ls = new ArrayList<Integer>(Arrays.asList(5,4,3,2,1));
selectionSort ss = new selectionSort();
ss.selection(ls);
System.out.println(ls.toString());
}
private static void selection(List<Integer> ls){
int index=0;
int temp;
for (int i=0;i< ls.size()-1;i++){
for (int j=i;j<ls.size();j++){
if (ls.get(i) > ls.get(j)){
index = j;
}
}
temp = ls.get(i);
ls.set(i, ls.get(index));
ls.set(index, temp);
}
}
}
插入排序
- 算法步驟
將第一待排序序列第一個(gè)元素看做一個(gè)有序序列撰糠，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
從頭到尾依次掃描未排序序列辩昆，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置阅酪。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面汁针。）
-
動(dòng)圖演示
image
package sorted;
public class InsertSort{
public static void main(String[] args) {
int[] array = {5,4,3,2,1};
InsertSort is = new InsertSort();
is.insertSort(array);
for (int num:
array) {
System.out.println(num);
}
}
public static void insertSort(int[] array){
int insertVal = 0;
int insertIndex = 0;
for (int i=1;i<array.length;i++) {
insertIndex = i;
insertVal = array[i];
while(insertIndex>0 && insertVal<array[insertIndex-1]){
array[insertIndex] = array[insertIndex-1];//將大的數(shù)后移术辐，不插插入值
insertIndex--;
}
array[insertIndex] = insertVal;//最后插入值
}
}
}
希爾排序
希爾排序，也稱(chēng)遞減增量排序算法施无，是插入排序的一種更高效的改進(jìn)版本辉词。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)帆精，效率高较屿，即可以達(dá)到線(xiàn)性排序的效率隧魄；
但插入排序一般來(lái)說(shuō)是低效的卓练，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位；
希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序购啄，待整個(gè)序列中的記錄"基本有序"時(shí)襟企，再對(duì)全體記錄進(jìn)行依次直接插入排序。
- 算法步驟
選擇一個(gè)增量序列 t1狮含，t2顽悼，……，tk几迄，其中 ti > tj, tk = 1蔚龙；
按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序映胁；
每趟排序木羹，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序坑填。僅增量因子為 1 時(shí)抛人，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度脐瑰。
-
動(dòng)圖演示
image
image.png
package sorted;
import java.util.Arrays;
public class Shell {
public static void main(String[] args){
int [] array = {5,9,4,7,8,6,0,3,2,1};
Shell shell = new Shell();
shell.shellSort(array);
System.out.println(Arrays.toString(array));
}
public static void shellSort(int [] array){
int len = array.length;
int l = array.length;
int value = 0;
int index = 0;
while(l>=1){
l = (int)l/2;
for (int i=0;i<l;i++){
for(int j = i+l;j<len;j+=l){
value = array[j];
index = j;//希爾改進(jìn)位移式妖枚，交換式效率低
while(index>i && value<array[index-l]){
array[index] = array[index-l];
index = index-l;
}
array[index] = value;
}
}
}
}
}
快速排序（重點(diǎn)）
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下苍在，排序 n 個(gè)項(xiàng)目要 Ο(nlogn) 次比較绝页。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)寂恬。事實(shí)上抒寂，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)掠剑。
快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）屈芜。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看朴译，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法井佑。
快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦?tīng)到這個(gè)名字你就知道它存在的意義眠寿，就是快躬翁，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了盯拱。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)盒发，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好狡逢，可是這是為什么呢宁舰，我也不知道。好在我的強(qiáng)迫癥又犯了奢浑，查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競(jìng)賽》上找到了滿(mǎn)意的答案：
快速排序的最壞運(yùn)行情況是 O(n2)蛮艰，比如說(shuō)順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn)雀彼，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小壤蚜，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以徊哑，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言袜刷，快速排序總是優(yōu)于歸并排序。
- 算法步驟
從數(shù)列中挑出一個(gè)元素莺丑，稱(chēng)為 "基準(zhǔn)"（pivot）;
重新排序數(shù)列著蟹，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后草则，該基準(zhǔn)就處于數(shù)列的中間位置钢拧。這個(gè)稱(chēng)為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序炕横；
此圖為雙邊循環(huán)法源内，還有單邊循環(huán)法（復(fù)習(xí)的時(shí)候?qū)崿F(xiàn)！７莸睢Ｄさ觥！）
還有非遞歸實(shí)現(xiàn)方式卿嘲，后續(xù)探究颂斜，
package sorted;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int [] array = {5,9,4,7,8,6,0,3,2,1,-100};
quickSort(array,0, array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int []array, int start,int end){
int pivot = array[(start+end)>>1];
int left = start;
int right = end;
int temp = 0;
while(left<right){
while(array[left]<pivot){
left++;
}
while(array[right]>pivot){
right--;
}
if(left>=right){
break;
}
temp = array[right];
array[right] = array[left];
array[left] = temp;
if(array[left] == pivot){
right--;
}
if(array[right] == pivot){
left++;
}
}
if(left==right){
left++;
right--;
}
if(start<right) {
quickSort(array, start, right);
}
if (left<end) {
quickSort(array, left, end);
}
}
}
