每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来。
void bubbleSort(int arr[],int n) { bool swapp = true; while(swapp){ swapp = false; for (int i = 0; i < n; i++) { if (arr[i] > a[i+1] ){ a[i] += a[i+1]; a[i+1] = a[i] - a[i+1]; a[i] -=a[i+1]; swapp = true; } } } }
空间效率：O(1)
时间效率：最好情况：O(n) 平均情况：O(N^2) 最坏情况：O(N^2)
稳定性（相同元素相对位置变化情况）：稳定
快排是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
根据实现算法的不同，元素的选择一般有如下几种：
1. 永远选择第一个元素
2. 永远选择最后一个元素
3. 随机选择元素
4. 取中间值
int partition(int arr[], int low, int high){ int tmp = arr[low]; while (low < high) { while (low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; } arr[low] = tmp; return low; } void quick_sort(int arr[], int low, int high){ if(low < high){ int pivotpos = partition(arr,low,high); quick_sort(arr,low,pivotpos-1); quick_sort(arr,pivotpos+1,high); } }
算法导论中提供了另一种 partition 的思路
int partition(int arr[], int low, int high){ int pivot = arr[high]; int i = low - 1; for(int j = low; j <= high - 1; j++){ if(arr[j] <= pivot){ i++; arr[i] += arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return (i+1); }
空间效率：最好情况: O(log2(N+1)) 平均情况 : O(log2N) 最坏情况 ： O(log2N)
时间效率：最好情况：O(Nlog2N) 平均情况：O(Nlog2N) 最坏情况：O(N2)
稳定性（相同元素相对位置变化情况）：稳定
原文：https://www.cnblogs.com/wanghao-boke/p/10421133.html