首页 > 代码库 > C/C++ 排序&&查找算法（面试）

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

2024-07-13 19:14:26   223人阅读

一、排序

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         else17         {18             low = mid + 1;19         }20     }21 }


联系
我们