快速排序（QuickSort）
时间复杂度：最好情况O(nlogn)*，最坏 O(n^2)
-
算法思想
转自《坐在马桶上看算法：快速排序》
- 最容易理解的写法
//快速排序
void quick_sort1(int s[],int low,int high)
{
int i = low, j = high, x = s[low];//x存基准数
if (low > high) {
return;
}//递归出口
while (i<j) {
while (i < j && s[j] >= x) // 从右向左找第一个小于等于x的数
j--;
while (i < j && s[i] <= x) // 从左向右找第一个大于等于x的数（一定要有等于，否则无法跳过第一个基准数）
i++;
if (i<j) {
int temp = s[i];
s[i] = s[j];
s[j] = temp;//交换
}
}
s[low] = s[i];
s[i] = x;//一趟循环结束后，将基准数与s[i]交换
quick_sort1(s, low, i-1); // 递归调用
quick_sort1(s, i+1, high);
}
- 快速排序（分离出partition算法）
int partition(int s[],int low,int high) {
int i = low,j = high,x = s[low];//x存基准数
while (i<j) {
while (i < j && s[j] >= x) // 从右向左找第一个小于等于x的数
j--;
while (i < j && s[i] <= x) // 从左向右找第一个大于等于x的数（一定要有等于，否则无法跳过第一个基准数）
i++;
if (i<j) {
int temp = s[i];
s[i] = s[j];
s[j] = temp;//交换
}
}
s[low] = s[i];
s[i] = x;//将基准数与s[i]交换
return i;//返回基准数所在数组位置的下标
}
void quick_sort(int s[],int low,int high) {
if (low < high) {
int i = partition(s, low, high);//记下基准位置，在把其左右两边递归
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]); //将中间的这个数和第一个数交换
int i = low, j = high, x = s[low];
while (i<j) {
while (i<j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort_up2(s, low, i-1); // 递归调用
quick_sort_up2(s, i+1, high);
}
}
二分查找(折半查找,Binary Search)
时间复杂度O(log2n)
- 算法思想
(1)首先确定整个查找区间的中间位置mid=(low+high)/2;
(2)用待查关键字值与中间位置关键字值进行比较；
若相等，则查找成功；
若大于，则在后半个区域中继续进行折半查找。
若小于，则在前半个区域中继续进行折半查找。
查找成功，返回关键字所在数组下标，没找到返回-1；
- 用递归实现
/**
* 递归方法实现二分查找法.
* @param Array数组
* @param low 数组第一位置
* @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;
}
- 非递归实现
//二分查找非递归方式
int HalfSearch(int a[],int low,int high,int key)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;//二分点
if(a[mid]==key) return mid;
else if(a[mid]<key) low=mid+1;
else high=mid-1;
}
return -1;
}
and so on...
