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

浏览数：23 / 时间：2015年06月08日

一、排序

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 void InsertSort(int arr[], int count)
 2 {
 3      for (int i = 1; i < count; ++i)
 4      {
 5          if (arr[i] < arr[i - 1])
 6          {
 7              int j = 0;
 8              int key= arr[i];
 9              arr[i] = arr[i - 1];
10              for (j = i - 2; ((j >= 0) && (key< arr[j])); --j)
11              {
12                      arr[j + 1] = arr[j];
13              }
14              arr[j + 1] = key;
15          }
16      }
17 }

插入排序---递归实现

 1 void Insert(int *a,int n)//把数组a的第n个数插入前n-1个数中，注意前n-1个数已经是排好序的了
 2  {
 3      int i=n-1;
 4       int key=a[n];
 5       while((i>=0)&&(key<a[i]))
 6       {
 7           a[i+1]=a[i];
 8           i--;
 9       }
10      a[i+1]=key;
11      return;
12  }
13  
14  void InsertionSort(int *a,int n)//递归插入，跟求阶乘的思想一样，前n-1个排好序的数组，是建立在前n-2个排好序的数组的基础上插出来的
15  {
16      if(n>0)
17      { 
18          Insert(a,n);
19          InsertionSort(a,n-1);
20      }
21      else 
22          return;
23  }

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 }