九大经典算法之冒泡排序、快速排序发布时间：2022/5/31 12:53:39
03 冒泡排序(Bubble Sort)
每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来。
普通版
void bubbleSort(int arr[],int n){//标准版
for(int i = 0; i 1; i++){
for(int j = 0; j 1 - i; j++){
if(arr[j] > arr[j+1]){
arr[j] += arr[j+1];
arr[j+1] = arr[j] - arr[j+1];
arr[j] -= arr[j+1];
}
}
}
}
进阶版
void bubbleSort(int arr[],int n)
{
bool swapp = true;
while(swapp){
swapp = false;
for (int i = 0; i ) { //这里的n要减1
if (arr > arr[i+1] ){
arr += a[i+1];
arr[i+1] = arr - arr[i+1];
arr -=a[i+1];
swapp = true;
}
}
}
}
空间效率：O(1)
时间效率：最好情况：O(n) 平均情况：O(N^2) 最坏情况：O(N^2)
稳定性（相同元素相对位置变化情况）：稳定
04 快速排序（Quick Sort）
快排是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
根据实现算法的不同，元素的选择一般有如下几种：
1. 永远选择第一个元素
2. 永远选择最后一个元素
3. 随机选择元素
4. 取中间值
int partition(int arr[], int low, int high){
int tmp = arr[low];
while (low high) {
while (low = tmp) {
high--;
}
arr[low] = arr[high];
while (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);
}
}
修改统一接口
void quickSort(int arr[],int n){
quick_sort(arr,0,n-1);
}
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);
}
}
int partition(int arr[],int low,int high){
int tmp = arr[low];
while(low high){
while(low = tmp){
high--;
}
arr[low] = arr[high];
while(low tmp){
low++;
}
arr[high] = arr[low];
}
arr[low] = tmp;
return low;
}
算法导论中提供了另一种 partition 的思路
int partition(int arr[], int low, int high){
int pivot = arr[high];
int i = low - 1;
for(int j = low; j 1; j++){
if(arr[j] pivot){
i++;
arr += arr[j];
arr[j] = arr - arr[j];
arr = arr - arr[j];
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i+1);
}
具体代码实现
int partition(int arr[],int low,int high){
int pivot = arr[high];
int i = low - 1;
for(int j = low; j 1; j++){
if(arr[j] pivot){
i++;
int temp = arr;
arr = arr[j];
arr[j] = temp;
//arr += arr[j]; 这种交换数值结果出错
//arr[j] = arr - arr[j];
//arr -= arr[j];
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
//arr[i+1] += arr[high];
//arr[high] = arr[i+1] - arr[high];
//arr[i+1] -= arr[high];
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
 |
