C/C++ 排序&&查找算法（面试）

一、排序

1.冒泡排序

 1 void BubbleSort(int array[],int n)
 2 {  
 3     int i=0; 
 4     int j=0; 
 5     int temp=0;
 6     int flag = 0;
 7     for(i=0;i<n - 1 ;i++)   /*外循环控制排序的总趟数*/
 8     {
 9         flag = 0;   /*本趟排序开始前，交换标志应为假*/
10        for(j=n-1;j > i;j--) /*内循环控制一趟排序的进行*/ 
11        {
12            if(array[j] < array[j-1] ) /*相邻元素进行比较，若逆序就交换*/
13            {
14              temp =array[j];
15              array[j] = array[j-1];
16              array[j-1] = temp;
17              flag = 1;                  /*发生了交换，故将交换标志置为真*/
18            }
19            
20        }
21         if (flag == 0)  /*本趟排序未发生交换，提前终止算法*/
22            break;
23     }
24 }

冒泡排序--递归实现

 1  void SortByRecursion( int *array, int n )
 2  {
 3       int i;
 4       if(1 == n)
 5       {
 6           return;
 7       }
 8       for(i = 0; i < n - 1; i++)
 9       {
10          if(array[i] > array[i + 1])
11               swap( &array[i], &array[i + 1]);
12      }
13      SortByRecursion( array, n - 1 );
14  }

2.插入排序

 1 //插入排序(非递归)  
 2 void InsertSort(int *pArr, int nLength)  
 3 {  
 4     if (pArr == NULL || nLength <= 0)  
 5     {  
 6         return;  
 7     }  
 8        
 9     int key = 0;  
10     int j=0;  
11     for (int i=1; i<nLength; i++)  
12     {  
13         if (pArr[i] < pArr[i-1])//当前带插入的元素比有序序列的最后一个元素小  
14         {  
15            key = pArr[i];  
16            for (j=i-1; j>=0&&key<pArr[j]; j--)  
17            {  
18                pArr[j+1] = pArr[j];             
19            }  
20            pArr[j+1] = key;  
21         }  
22     }  
23 }

插入排序---递归实现

 1 //插入排序(递归)  
 2 void InsertSortRecursively(int *pArr, int index, int nLength)  
 3 {  
 4     if (index >= nLength)  
 5     {  
 6         return;  
 7     }  
 8   
 9     int key = pArr[index];//记录当前待插入的元素    
10     int i=0;  
11     for (i=index-1; i>=0&&key<pArr[i]; i--)  
12     {  
13         pArr[i+1] = pArr[i];          
14     }  
15     pArr[i+1] = key;  
16     InsertSortRecursively(pArr, index+1, nLength);  
17 }

3.快速排序

 1 int PartSort(int arr[],int low, int high)
 2 {
 3     int key = arr[low];
 4     while(low < high)
 5     {
 6         while(low < high && arr[high] >= key)
 7             --high;
 8         arr[low] = arr[high];
 9         while(low < high && arr[low] <= key)
10           ++low;
11         arr[high] = arr[low];
12     }
13     arr[low] = key;
14     return low;
15 }
16 void QuickSort(int arr[],int low, int high)
17 {
18      if(low < high)
19      {
20          int pos = PartSort(arr, low, high);
21          QuickSort(arr, pos+1, high);
22          QuickSort(arr, low, pos-1);
23      }
24 }

二、查找

1.折半查找

 1 int  HalfFind(int arr[], int count,int key)
 2 {
 3     int low = 0;
 4     int high = count - 1;
 5     while(low <= high)
 6     {
 7         int mid = (low + high)/2;
 8         if (arr[mid] == key)
 9         {
10             return mid;
11         } 
12         else if(arr[mid] > key)
13         {
14             high = mid - 1 ;
15         }
16         else
17         {
18             low = mid + 1;
19         }
20     }
21 }