网站后台更新的内容出不来,国家高新技术企业名单,网站seo优化价格,网上买东西有哪些平台一个用来了解数据结构算法#xff08;各种排序#xff0c;列表#xff0c;树等#xff09;很友好的网站#xff1a; https://visualgo.net/en
该题目来自于牛客#xff1a;算法篇-排序问题
快排#xff08;必备#xff09;归并#xff08;体会分治#xff09;堆(自…一个用来了解数据结构算法各种排序列表树等很友好的网站 https://visualgo.net/en
该题目来自于牛客算法篇-排序问题
快排必备归并体会分治堆(自己建堆)
//快速排序 关键在于 partition函数可以自己参考一个模板我这个参考大话数据结构class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 将给定数组排序* param arr int整型vector 待排序的数组* return int整型vector*///1.快速排序vectorint MySort(vectorint arr) {// write code hereint left0;int rightarr.size()-1;QuickSort(arr,left,right);return arr;}int QuickTemp(vectorint arr,int left,int right){ int i left;int j right;int temp arr[left];while(ij){while(temparr[j]ij) --j;arr[i]arr[j];while(temparr[i]ij) i;arr[j]arr[i];}arr[i] temp;return i;}void QuickSort(vectorint arr,int left,int right){if(leftright){int midQuickTemp(arr,left,right);QuickSort(arr, left,mid-1);QuickSort(arr, mid1, right);}}
};//归并排序 关键在于构造一个数组 然后merge所以这个 merge函数是关键
class Solution {
public://归并排序vectorint MySort(vectorint arr) {MySortCore(arr,0,arr.size()-1);return arr;}void MySortCore(vectorintarr,int start,int end){if(startend) return;int middlestart((end-start)1);MySortCore(arr,start,middle);MySortCore(arr,middle1,end);Merge(arr,start,middle,end);}void Merge(vectorintarr,int start,int middle,int end){int* tmpnew int[end-start1];int leftstart;int rightmiddle1;int pTmp0; //辅助数组指针while(leftmiddle rightend){if(arr[left]arr[right])tmp[pTmp]arr[left];elsetmp[pTmp]arr[right];}while(leftmiddle)tmp[pTmp]arr[left];while(rightend)tmp[pTmp]arr[right];//排序完数组拷贝回原数组for(int i0;iend-start1;i)arr[starti]tmp[i];}
};
//堆排序分为两步建堆排序
//一些细节可以参考大话数据结构
//我这个堆是从下标为0开始的所以左子节点 left2*root1, right2*root1class Solution {
public://堆排序void Swap(inta,int b){int tmpa;ab;btmp;}void HeapAdjust(vectorintarr,int root,int len){int tmparr[root];for(int j2*root1;jlen;j2*j1){if(jlen-1 arr[j]arr[j1])j;if(tmparr[j])break;arr[root]arr[j];rootj;}arr[root]tmp;}vectorint MySort(vectorint arr) {for(int iarr.size()/2-1;i0;i--)HeapAdjust(arr,i,arr.size());for(int iarr.size()-1;i0;i--){Swap(arr[0],arr[i]);HeapAdjust(arr,0,i);}return arr;}
};小结 在做快排序的时候出现了超时问题解决办法 1、逻辑调整 2、把i/j–替换成i/–j。 3、使用递归前的函数传参最好不是计算式。 以下是其他友友的代码和注释写的很认真就贴了过来
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* 将给定数组排序* param arr int整型vector 待排序的数组* return int整型vector*/vectorint MySort(vectorint arr) {// write code heremySort1(arr);return arr;}// 1、快速排序通过// 时间复杂度O(logn)。空间复杂度是O(n)。// 主要是要找出标杆值中间值默认最后一个值为标杆值然后比它小的放左边比他大的放右边然后交换最后一位。就得到标杆值在中间的下标。
// 树从上往下排序// 不稳定算法void mySort1(vectorint arr) {quicksort(arr, 0, arr.size()-1);} void quicksort(vectorint arr, int left, int right) {if (left right) return;int pivotIndex partition(arr, left, right); // 标杆值所在的位置quicksort(arr, left, pivotIndex-1); // 左半边quicksort(arr, pivotIndex1, right); // 右半边}int partition(vectorint arr, int left, int right) {// 最后一个值当做标杆int counter left; // 记录小于标杆值的个数while (left right) {if (arr[left] arr[right]) { // 当前值和标杆值比较决定是放在左边还是右边swap(arr[left], arr[counter]);counter;}left;}swap(arr[counter], arr[right]); // 最后把标杆值移到中间位置然后返回下标。return counter;}// 2、归并排序通过// 时间复杂度O(logn)。空间复杂度是O(n)。// 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。// 树从下往上排序// 是稳定的算法void mySort2(vectorint arr) {mergeSort(arr, 0, arr.size()-1);} void mergeSort(vectorint arr, int left, int right) {if (left right) return;int mid left (right - left) / 2;mergeSort(arr, left, mid); // 递归 左半边mergeSort(arr, mid1, right); // 递归 右半边merge(arr, left, mid, right); // 合并两个有序的数组参考合并两个有序的链表}// 合并两个有序数组void merge(vectorint arr, int left, int mid, int right) {vectorint tmp(right-left1); // 开辟新的数组int i left, j mid1, k 0; // i左边数组的起始位置j右边数组的起始位置k已经放入新数组的个数while (i mid j right) { // 比较左右数组数值小的放入新数组中tmp[k] arr[i] arr[j] ? arr[i] : arr[j];}while (i mid) tmp[k] arr[i]; // 如果左半边数组没有排序完加入新数组while (j right) tmp[k] arr[j]; // 如果右半边数组没有排序完加入新数组for (i left, k 0; i right;) arr[i] tmp[k]; // 新数组数据放回到原来的数组中}// 3、堆排序通过// 时间复杂度O(logn)。空间复杂度是O(n)。// 不稳定算法void heapSort(vectorint arr) {priority_queueint,vectorint,greaterint q; //小顶堆for (int i 0; i arr.size(); i) {q.push(arr[i]);}for (int i 0; i arr.size(); i) {arr[i] q.top();q.pop();}}// 4、冒泡排序超时// 时间复杂度O(n2)空间复杂度O(1)// 从后往前排// 两两比较交换最大的放在后面稳定排序void bubbleSort(vectorint arr) {for (int i 0; i arr.size(); i) {for (int j 0; j arr.size()-i-1; j) {if (arr[j]arr[j1]) {swap(arr[j], arr[j1]);}}}}// 5、选择排序超时// 时间复杂度O(n2)空间复杂度O(1)// 从前往后排// 遍历数组找出最小值最小的放在前面不稳定排序void selectionSort(vectorint arr) {int minIndex 0;for (int i 0; i arr.size(); i) {minIndex i;for (int j i1; j arr.size(); j) {if (arr[j] arr[minIndex]) {minIndex j;}}swap(arr[i], arr[minIndex]);}}// 6、插入排序超时// 时间复杂度O(n2)空间复杂度O(1)// 从前往后排// 遍历数组找出一个值往排好的数组里面插入合适的位置。稳定排序void insetionSort(vectorint arr) {int preIndex 0;int currentVal 0;for (int i 1; i arr.size(); i) {preIndex i - 1;currentVal arr[i];while (preIndex 0 arr[preIndex] currentVal) {arr[preIndex1] arr[preIndex];preIndex--;}arr[preIndex1] currentVal;}}};
