常用算法1 - 快速排序 & 二分查找

时间:2023-01-29 15:07:22

1. 二分查找法:

二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回对应的数组下标,没有找到返回-1。

二分查找法要求数据为一组有序的序列(大到小或小到大),但实际给出的数据往往是无序的,这是就需要先进行排序;排序算法有很多,但最有效、快速的当属快速排序算法。

2. 快速排序算法

1). 思想

快速排序采用的思想是分治思想。

  1. 找出一个元素(理论上元素随意)作为基准(pivot);
  2. 对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置;
  3. 递归快速排序,将其他n-1个元素也调整到排序后的正确位置;
  4. 每个元素都是在排序后的正 确位置,排序完成.

所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

2). 步骤

常用算法1 - 快速排序 & 二分查找

(本图转自 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;
}