1. 二分查找法:
二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回对应的数组下标,没有找到返回-1。
二分查找法要求数据为一组有序的序列(大到小或小到大),但实际给出的数据往往是无序的,这是就需要先进行排序;排序算法有很多,但最有效、快速的当属快速排序算法。
2. 快速排序算法
1). 思想
快速排序采用的思想是分治思想。
- 找出一个元素(理论上元素随意)作为基准(pivot);
- 对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置;
- 递归快速排序,将其他n-1个元素也调整到排序后的正确位置;
- 每个元素都是在排序后的正 确位置,排序完成.
所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
2). 步骤
(本图转自 https://www.cnblogs.com/MOBIN/p/4681369.html,做部分修改)
3. 示例代码
/*
* This is used for bisection search
* 1. sort the numbers in array
* 2. bisection search the sorted array
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SEARCH 1
/*
* For sort the number array
*/
int partition(int array[], int start, int end)
{
int left_point, right_point;
int pivot; //Basic point
left_point = start;
right_point = end;
pivot = array[left_point];
while(left_point < right_point)
{
while((right_point > left_point) && (array[right_point] >= pivot))
{
right_point-- ;
}
array[left_point] = array[right_point];
while((right_point > left_point) && (array[left_point] <= pivot))
{
left_point++ ;
}
array[right_point] = array[left_point];
}
array[left_point] = pivot;
return left_point; //the left_point is where pivot place
}
void quick_sort(int array[], int start, int end)
{
if(start >= end)
{
return ;
}
int mid = 0;
mid = partition(array, start, end);
quick_sort(array, start, mid-1);
quick_sort(array, mid+1, end);
}
/*
* Bisection of the array to search the number
*/
int bisection(int array[], int key, int start, int end)
{
if(start >= end)
{
return -1;
}
int mid = (start+end)/2;
if(array[mid] == key)
{
return mid;
}
else if(array[mid] < key)
{
bisection(array, key, mid+1, end);
}
else if(array[mid] > key)
{
bisection(array, key, start, mid);
}
}
/*
* Main function, only for test
*/
int main(int argc, char *argv[])
{
int array[10] = {10,9,8,7,6,5,4,3,2,1};
quick_sort(array, 0, 9);
int i=0;
for(i=0; i<10; i++)
{
printf("array[%d]=%d\n",i,array[i]);
}
int pos=0;
pos = bisection(array, SEARCH, 0, 9);
if(-1 == pos)
{
printf("There was no key=%d\n",SEARCH);
}
else
{
printf("The key=%d, pos is %d\n", SEARCH,pos);
}
return 0;
}