快速排序（QuickSort）
時(shí)間復(fù)雜度：最好情況O(nlogn)*论皆，最壞 O(n^2)
-
算法思想
轉(zhuǎn)自《坐在馬桶上看算法：快速排序》
- 最容易理解的寫法
//快速排序
void quick_sort1(int s[],int low,int high)
{
int i = low, j = high, x = s[low];//x存基準(zhǔn)數(shù)
if (low > high) {
return;
}//遞歸出口
while (i<j) {
while (i < j && s[j] >= x) // 從右向左找第一個(gè)小于等于x的數(shù)
j--;
while (i < j && s[i] <= x) // 從左向右找第一個(gè)大于等于x的數(shù)（一定要有等于嘲更，否則無法跳過第一個(gè)基準(zhǔn)數(shù)）
i++;
if (i<j) {
int temp = s[i];
s[i] = s[j];
s[j] = temp;//交換
}
}
s[low] = s[i];
s[i] = x;//一趟循環(huán)結(jié)束后宰衙，將基準(zhǔn)數(shù)與s[i]交換
quick_sort1(s, low, i-1); // 遞歸調(diào)用
quick_sort1(s, i+1, high);
}
- 快速排序（分離出partition算法）
int partition(int s[],int low,int high) {
int i = low,j = high,x = s[low];//x存基準(zhǔn)數(shù)
while (i<j) {
while (i < j && s[j] >= x) // 從右向左找第一個(gè)小于等于x的數(shù)
j--;
while (i < j && s[i] <= x) // 從左向右找第一個(gè)大于等于x的數(shù)（一定要有等于，否則無法跳過第一個(gè)基準(zhǔn)數(shù)）
i++;
if (i<j) {
int temp = s[i];
s[i] = s[j];
s[j] = temp;//交換
}
}
s[low] = s[i];
s[i] = x;//將基準(zhǔn)數(shù)與s[i]交換
return i;//返回基準(zhǔn)數(shù)所在數(shù)組位置的下標(biāo)
}
void quick_sort(int s[],int low,int high) {
if (low < high) {
int i = partition(s, low, high);//記下基準(zhǔn)位置例朱，在把其左右兩邊遞歸
quick_sort(s, low, i-1);
quick_sort(s, i+1, high);
}
}
- 最簡單的寫法
//快速排序
void quick_sort_up2(int s[],int low,int high)
{
if (low < high) {
//Swap(s[low], s[(low + high) / 2]); //將中間的這個(gè)數(shù)和第一個(gè)數(shù)交換
int i = low, j = high, x = s[low];
while (i<j) {
while (i<j && s[j] >= x) // 從右向左找第一個(gè)小于x的數(shù)
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x) // 從左向右找第一個(gè)大于等于x的數(shù)
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort_up2(s, low, i-1); // 遞歸調(diào)用
quick_sort_up2(s, i+1, high);
}
}
二分查找(折半查找,Binary Search)
時(shí)間復(fù)雜度O(log2n)
- 算法思想
(1)首先確定整個(gè)查找區(qū)間的中間位置mid=(low+high)/2;
(2)用待查關(guān)鍵字值與中間位置關(guān)鍵字值進(jìn)行比較删顶；
若相等阎姥，則查找成功捐凭；
若大于，則在后半個(gè)區(qū)域中繼續(xù)進(jìn)行折半查找凳鬓。
若小于茁肠，則在前半個(gè)區(qū)域中繼續(xù)進(jìn)行折半查找。
查找成功缩举，返回關(guān)鍵字所在數(shù)組下標(biāo)垦梆，沒找到返回-1；
- 用遞歸實(shí)現(xiàn)
/**
* 遞歸方法實(shí)現(xiàn)二分查找法.
* @param Array數(shù)組
* @param low 數(shù)組第一位置
* @param high 最高
* @param key 要查找的值.
* @return 返回值.
*/
int BinarySearch(int Array[],int low,int high,int key)
{
if (low<=high) {
int mid = (low+high)/2;
if(key == Array[mid])
return mid;//遞歸出口
else if(key < Array[mid])//移動low和high
return BinarySearch(Array,low,mid-1,key);//key在左半邊
else if(key > Array[mid])
return BinarySearch(Array,mid+1,high,key);//key在右半邊
}
return -1;
}
- 非遞歸實(shí)現(xiàn)
//二分查找非遞歸方式
int HalfSearch(int a[],int low,int high,int key)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;//二分點(diǎn)
if(a[mid]==key) return mid;
else if(a[mid]<key) low=mid+1;
else high=mid-1;
}
return -1;
}
and so on...
