吴江开发区建设局网站,做个商城小程序需要多少钱,wordpress width,湖北网站建设路03 冒泡排序(Bubble Sort) 每次选择两个元素#xff0c;按照需求进行交换#xff08;比如需要升序排列的话#xff0c;把较大的元素放在靠后一些的位置#xff09;#xff0c;循环 n 次#xff08;n 为总元素个数#xff09;#xff0c;这样小的元素会不断 “冒泡” 到… 03 冒泡排序(Bubble Sort) 每次选择两个元素按照需求进行交换比如需要升序排列的话把较大的元素放在靠后一些的位置循环 n 次n 为总元素个数这样小的元素会不断 “冒泡” 到前面来。 普通版 void bubbleSort(int arr[],int n){//标准版for(int i 0; i n - 1; i){for(int j 0; j n - 1 - i; j){if(arr[j] arr[j1]){arr[j] arr[j1];arr[j1] arr[j] - arr[j1];arr[j] - arr[j1];}}}
} 进阶版 void bubbleSort(int arr[],int n)
{bool swapp true;while(swapp){swapp false;for (int i 0; i n - 1; i) { //这里的n要减1if (arr[i] arr[i1] ){arr[i] a[i1];arr[i1] arr[i] - arr[i1];arr[i] -a[i1];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 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,pivotpos1,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,pivotpos1,high);}
}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;
} 算法导论中提供了另一种 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 (i1);
} 具体代码实现 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;int temp arr[i];arr[i] arr[j];arr[j] temp;//arr[i] arr[j]; 这种交换数值结果出错 //arr[j] arr[i] - arr[j];//arr[i] - arr[j];}}int temp arr[i1];arr[i1] arr[high];arr[high] temp;//arr[i1] arr[high];//arr[high] arr[i1] - arr[high];//arr[i1] - arr[high];return i1;} 空间效率最好情况: O(log2(N1)) 平均情况 : O(log2N) 最坏情况 O(log2N) 时间效率最好情况O(Nlog2N) 平均情况O(Nlog2N) 最坏情况O(N2) 稳定性相同元素相对位置变化情况稳定 转载于:https://www.cnblogs.com/wanghao-boke/p/10421133.html
