查找和排序

Julia999

折半查找（每次取一半）

排序：
冒泡（两个两个进行比较，以满足条件的排序交换位置）
插入（一个一个往前插，保证前面的插入的都有序）
选择（从所有的元素里面找到最小的跟第一个互换，把剩下找到最小的跟第二个互换.....）
快速排序（先找到第一个元素的确切位置，这个时候将元素分成了两半，分别找到左边的第一个元素的确切位置，以及右边第一个元素的确切位置，不断重复操作（递归的思想））
归并排序（先两个两个拍，再四个四个排，再八个八个排....，最终整体排）


在这里给出快速排序的代码：

1. #include<stdio.h>
   
2. 
   
3. void QuickSort(int *a,int low,int high)
   
4. {
   
5.         int pos;
   
6.         if(low<high)
   
7.         {
   
8.                 pos=FindPos(a,low,high);
   
9.                 QuickSort(a,low,pos-1);
   
10.                 QuickSort(a,pos+1,high);
    
11.         }
    
12. }
    
13. 
    
14. 
    
15. int FindPos(int *a,int low,int high)
    
16. {
    
17.         int val=a[low];
    
18.         while(low<high)
    
19.         {
    
20.                 while(low<high&&a[high]>=val)
    
21.                 {
    
22.                         --high;
    
23.                 }
    
24.                 a[low]=a[high];
    
25. 
    
26.                 while(low<high&&a[low]<=val)
    
27.                 {
    
28.                         ++low;
    
29.                 }
    
30.                 a[high]=a[low];
    
31.         }//终止外循环之后，low和high是相等的
    
32.         a[low]=val;
    
33. 
    
34.         return low;
    
35. }
    
36. 
    
37. 
    
38. int main()
    
39. {
    
40.         int a[6]={2,1,0,5,4,3};
    
41.         int i;
    
42.         QuickSort(a,0,5);  //第二个参数表示第一个元素的下标，第三个参数表示最后一个元素的下标
    
43.         for(i=0;i<6;i++)
    
44.         {
    
45.                 printf("%d",a[i]);
    
46.         }
    
47.         printf("\n");
    
48.         return 0;
    
49. }

复制代码

排序和查找的关系
排序是查找的前提
排序是重点