---

排序算法

冒泡排序法二分查找法快速排序

---

1. 冒泡排序法

冒泡排序只需两层循环，外层循环控制冒泡的趟数，内层循环控制冒泡的方式，即用相邻两个元素进行比较，不满足则进行交换直至区间末尾。冒泡排序法外循环：冒泡的总趟数 N-1,每冒泡一次只能将一个元素排好，最后一趟只剩一个元素无需再冒泡，因此总的冒泡趟数为N-1.冒泡排序法内循环：用相邻进行比较，不满足则进行交换。需要N-1次比较。此时这种冒泡排序的时间复杂度为O(N^2)。特殊情况：若遇到某趟排序若已有序，那么就不再需要冒泡，就像下面这种情况。那么设置flag标签flag=1，若它在此趟冒泡中有交换，则flag被置为0。此趟冒泡结束后检测flag,flag未被改变则说明此趟排序已经有序，直接break跳出循环，不再进行冒泡。时间复杂度O(N^2)空间复杂度O(1)稳定性：稳定（没有间隔区间进行交换，所以稳定） //冒泡排序选择最大的（由小到大排列） n为数组长度 void BubbleSort(int arr[], int n) { for(int i=0; i<n-1; ++i) //总趟数 { int flag = 1; //假设这一趟排序的数据已经有序 for(int j=0; j<n-i-1; ++j) //每走一趟，遍历的元素少一个 { if(arr[j] > arr[j+1]) //前面的元素要是比后面的元素大，则进行交换 { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; flag = 0; } } if(1 == flag) //说明已经有序 { berak; } } }

---

2. 二分查找法

二分查找的前提条件是有序数列，普通查找则不需要。查找到返回该元素的下标，否则返回-1。普通查找的时间复杂度为O(N),二分查找的时间复杂度为O(log(N))N/2/2···/2=1，2^m=N(m为折半查找的次数)，那么m=log2(N)，二分查找的时间复杂度就为O(log2(N))。 int Find(int arr[], int n, int key) //查找指定元素所在位置 { for(int i=0; i<n; ++i) { if(arr[i] == key) //如果指定元素key与数组中的某元素arr[i]相等，则返回它的下标i return i; } return -1; //否则返回-1，表示未查找到与它相等的元素 } //二分法查找指定元素所在位置（前提条件是先按从小到大进行排列） int BinarySearch1(int arr[], int size, int key) { int low = 0; //设置低下标 int high = size-1; //设置高下标 int mid; while(low <= high) //一旦高下标小于低下标结束while循环 { mid = low+(high-low)>>1; //设置中间下标 if(key < arr[mid]) //如果指定元素比中间下标的值小 high = mid-1; //则把中间下标-1给高下标 else if(key > arr[mid]) //如果指定元素比中间下标的值大 low = mid+1; //则把中间下标+1给低下标 else //否则返回 中间下标 return mid; } return -1; //返回-1则表示在该数组中未找到该指定元素 } BinarySearch1注意以下5个点： low=0; high=size-1; // [ ] 闭区间，high为最后一个元素的下标 low <= high; mid= low+(high-low)>>1; high=mid-1; low=mid+1;

其示意图如下图所示：

int BinarySearch2(int arr[], int size, int key) { int low = 0; //设置低下标 int high = size; //设置高下标 int mid; while(low < high) //一旦高下标小于低下标结束while循环 { mid = low+(high-low)>>1; //设置中间下标 if(key < arr[mid]) //如果指定元素比中间下标的值小 high = mid; //则把中间下标-1给高下标 else if(key > arr[mid]) //如果指定元素比中间下标的值大 low = mid+1; //则把中间下标+1给低下标 else //否则返回 中间下标 return mid; } return -1; //返回-1则表示在该数组中未找到该指定元素 } BinarySearch2注意以下5个点： low=0; high=size; // [ ） 左闭右开，high为最后一个元素的下一个位置 low < high; mid= low+(high-low)>>1; high=mid; low=mid+1;

其示意图如下图所示：

---

3. 快速排序

快速排序的框架（递归）

void QuickSort(int array[],int left,int right) { if(righ-left>1) { int div=partion(array,left,right); QuickSort(array,left,div); QuickSort(array,div+1,right); } }

三种数据分割方法 1.hoare法

int partion(int array[],int left,int right) { int begin=left; int end=right-1; int key=array[right-1]; }

2.挖坑法 3.前后指针法

---