快速排序
速度快区转，占內(nèi)存（迭代）
- 先從后往前找最小的函似，再從前往后找最大的阴绢；
- 在數(shù)據(jù)中選取一個(gè)元素，將所有比其大的放在左邊艰躺，將所有比其小的放在右邊呻袭；
- 然后再將左邊的和右邊的分別選出一個(gè)元素，進(jìn)行上述操作直到排序結(jié)束腺兴。
具體實(shí)施&思想
1.對(duì)所有待排序元素左电，設(shè)定i為最左邊下標(biāo)，j為最右邊下標(biāo)页响，k為選取的元素（arr[i]篓足，即將arr[i]“挖掉”，i為“坑”）闰蚕。
2.從j開始栈拖，j--，找出<=k的没陡，令arr[i] = arr[j],相當(dāng)于將j元素“挖掉”涩哟，填到i，此時(shí)j為“坑”盼玄；接著從i開始贴彼，i++，找>=k的埃儿，令arr[j] = arr[i]锻弓，即將i元素“挖掉”，填到j(luò)蝌箍，此時(shí)i為“坑”青灼。
3.重復(fù)上面步驟直到i==j，這時(shí)k左邊的元素（m）都比k小妓盲，k右邊的元素（n）都比k大
4.令arr[i] = k杂拨，將arr[i]的“坑”填住。
5.將m悯衬，n分為兩個(gè)數(shù)據(jù)集弹沽，再進(jìn)行1~3操作，直到m筋粗，n中只有一個(gè)元素策橘，排序結(jié)束。
void quick(int i,int j,int[] arr){
if (i < j) {
int l = i;//前
int r = j;//后
int k = arr[i];//把初始的元素提取出來娜亿，產(chǎn)生了一個(gè)“坑”
//這里的j>i是為了控制循環(huán)結(jié)束------只要j==i丽已，一輪循環(huán)就會(huì)結(jié)束
while (j > i) {
//j > l保證j不會(huì)向右越界，arr[j] > k是為了從后向前尋找比k小的元素
while (arr[j] >= k&& j > i) {
j--;
}
//一旦有比k小的元素买决，就將他存到k上次挖出的“坑”里面沛婴，此時(shí)在arr[j]里面生成一個(gè)“坑”
arr[i] = arr[j];
//i < r保證i不會(huì)向左越界吼畏，arr[i] < k是為了從前向后尋找比k大的元素
while (arr[i] < k&&j > i) {
i++;
}
//用剛剛發(fā)現(xiàn)的比k大的元素填到之前在k的后面挖出的“坑”里面，此時(shí)在k的前面arr[i]處挖出一個(gè)“坑”
arr[j] = arr[i];
}
//將剛才的“坑”填上嘁灯，至此泻蚊，一輪循環(huán)結(jié)束，以k分隔了所有大于/小于他的元素
arr[i] = k;
//進(jìn)行下一輪遍歷
quick(l,i -1,arr);
quick(i + 1, r, arr);
}
}