每次冒泡，把一个最大的数挤到无序部分的最后去。
如果遍历整个无序区间期间时，一次交换都没发生说明无序区间是有序的
void BubbleSort(int array[], int size) { for (int i = 0; i < size; i++) { int isSorted = 1; for (int j = 0; j < size - 1 - i; j++) { if (array[j] > array[j + 1]) { Swap(array, j, j + 1); isSorted = 0; } } if (isSorted == 1) { return; } } }最好情况：时间复杂度O(n)
最坏情况：O(n^2)
空间复杂度O(1)
冒泡排序是一种稳定的排序算法
任取待排序元素序列中的某元素作为基准值，按照排序码将待排序集合分割成两子序列，左子序列所有元素均小于基准值，右子序列中所有元素均大于基准值，左右子序列重复该过程，直到所有元素都排列在相应的位置上。
按照基准值将区间分成左右子序列
void _QuickSort(int array[],int low,int high) { //区间长度为0， if (low > high) { return; } //区间长度为1，表示区间内数已经有序 if (low == high) { return; } //找基准值，选最左边，基准值下边是low //遍历整个区间，小的放左，大的放右，返回基准值所在下标 int pivotIdx = Partition_3(array, low, high); //分治算法，分别处理两个区间 _QuickSort(array, low, pivotIdx-1); _QuickSort(array, pivotIdx + 1, high); }将区间按照基准值划分为左右两半部分的常见方式：
hoare版本
int Partition_1(int array[], int low, int high) { int begin = low;//begin从low开始 int end = high; int pivot = array[low]; while (begin < end) { //如果基准值放在左边，需要从右边开始走 while (begin<end&&array[end] >= pivot) { end--; } if (begin == end) { return; } while (begin < end&&array[begin] <= pivot) { begin++; } Swap(array, begin, end); } Swap(array, low, begin); return begin; }挖坑法
int Partition_2(int array[], int low, int high) {//挖坑法 int begin = low;//begin从low开始 int end = high; int pivot = array[low];//坑的下标是begin while (begin < end) { //如果基准值放在左边，需要从右边开始走 while (begin<end&&array[end] >= pivot) { end--; } array[begin] = array[end]; while (begin < end&&array[begin] <= pivot) { begin++; } array[end] = array[begin]; } array[begin] = pivot; return begin; }前后下标法
int Partition_3(int array[], int low, int high) { int d = low + 1; int i = low + 1; int pivot = array[low]; while (i < high) { if (array[i] < pivot) { Swap(array, d, i); d++; } i++; } Swap(array, d - 1, low); return d - 1; }
