百度网游排行榜,青岛官网优化推广,555建筑人才网,WordPress添加网页背景图片目录
OJ链接
一、直接插入排序
二、希尔排序
三、直接选择排序
常规#xff1a; 第二种#xff1a;
四、 堆排序
五、冒泡排序
六、快速排序
常规#xff1a;
三路划分优化效率
七、归并排序
八、计数排序 OJ链接
一、直接插入排序 class Solution {
pub…
目录
OJ链接
一、直接插入排序
二、希尔排序
三、直接选择排序
常规 第二种
四、 堆排序
五、冒泡排序
六、快速排序
常规
三路划分优化效率
七、归并排序
八、计数排序 OJ链接
一、直接插入排序 class Solution {
public:vectorint sortArray(vectorint nums) {for(int i0;inums.size()-1;i){int endi;int tmpnums[i1];while(end0){if(nums[end]tmp){nums[end1]nums[end];--end;}elsebreak;}nums[end1]tmp;}return nums;}
}; 二、希尔排序 class Solution {
public:vectorint sortArray(vectorint nums) {int gapnums.size();while(gap1){gapgap/31;for(int i0;inums.size()-gap;i){int endi;int tmpnums[endgap];while(end0){if(nums[end]tmp){nums[endgap]nums[end];end-gap;}elsebreak;}nums[endgap]tmp;}}return nums;}
}; 三、直接选择排序
常规 class Solution {
public:vectorint sortArray(vectorint nums) {int i,j,minIndex,temp;for(i0;inums.size()-1;i){minIndexi;for(ji1;jnums.size();j){if(nums[j]nums[minIndex])minIndexj;}tempnums[i];nums[i]nums[minIndex];nums[minIndex]temp;}return nums;}
}; 第二种 class Solution {
public:vectorint sortArray(vectorint nums) {int begin0,endnums.size()-1;while(beginend){int maxibegin,minibegin;for(int ibegin;iend;i){if(nums[i]nums[maxi])maxii;if(nums[i]nums[mini])minii;}swap(nums[begin],nums[mini]);if(beginmaxi)maximini;swap(nums[maxi],nums[end]);begin;--end;}return nums;}
};
四、 堆排序 class Solution {
public:void AdjustDown(vectorint a,int n,int parent){int childparent*21;while(childn){if(child1na[child1]a[child])child;if(a[child]a[parent]){swap(a[child],a[parent]);parentchild;childparent*21;}else{break;}}}vectorint sortArray(vectorint nums) {for(int i(nums.size()-1-1);i0;i--){AdjustDown(nums,nums.size(),i);}int endnums.size()-1;while(end0){swap(nums[0],nums[end]);AdjustDown(nums,end,0);--end;}return nums;}
};
五、冒泡排序 class Solution {
public:vectorint sortArray(vectorint nums) {for (int j 0; j nums.size(); j){bool exchange false;for (int i 1; i nums.size() - j; i){if (nums[i - 1] nums[i]){int tmp nums[i];nums[i] nums[i - 1];nums[i - 1] tmp;exchange true;}}if (exchange false){break;}}return nums;}
};
六、快速排序
常规 class Solution {
public:int GetMidIndex(vectorint a, int left, int right){int mid (left right) 1;if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}}void QuickSort(vectorint a, int begin, int end){if (begin end)return;int keyi PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}int PartSort3(vectorint a, int left, int right){int midi GetMidIndex(a, left, right);swap(a[left], a[midi]);int prev left;int cur left 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){swap(a[prev], a[cur]);}cur;}swap(a[prev], a[keyi]);keyi prev;return keyi;}vectorint sortArray(vectorint nums) {QuickSort(nums,0,nums.size()-1);return nums;}
};
三路划分优化效率
class Solution {
public:int GetMidIndex(vectorint a, int left, int right){int mid left (rand()%(right-left));if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}else // a[left] a[mid]{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return right;}else{return left;}}}void QuickSort(vectorint a, int begin, int end){if (begin end)return;int left begin;int right end;int cur left 1;int midi GetMidIndex(a, left, right);swap(a[left], a[midi]);int key a[left];while (cur right){if (a[cur] key){swap(a[left], a[cur]);left;cur;}else if (a[cur] key){swap(a[right], a[cur]);--right;}else{cur;}}QuickSort(a, begin, left - 1);QuickSort(a, right 1, end);}vectorint sortArray(vectorint nums){srand(time(0));QuickSort(nums, 0, nums.size() - 1);return nums;}
}; GetMidIndex这个方法用于在快速排序的过程中选择一个基准元素。它首先随机选择一个索引mid然后比较数组a在left、mid和right这三个位置的元素返回这三个元素中的中位数的索引。这种方式可以有效地避免在处理近乎有序的数组时快速排序退化为O(n^2)的情况。 QuickSort这是快速排序的主要方法。它首先调用GetMidIndex方法获取基准元素的索引然后将基准元素与数组的第一个元素交换位置接着遍历数组将小于基准的元素放到左边大于基准的元素放到右边等于基准的元素不动。最后递归地对基准元素左边和右边的子数组进行同样的操作。 sortArray这是对外的接口方法它首先初始化随机数种子然后调用QuickSort方法对输入的数组nums进行排序最后返回排序后的数组。
这段代码的主要优点是它使用了随机化的快速排序算法可以在平均情况下达到O(n log n)的时间复杂度而且它的空间复杂度为O(log n)因为它只需要递归调用栈的空间。
七、归并排序 class Solution {
public:void InsertSort(vectorint a, int begin, int end){for(int ibegin1; iend; i){int tmpa[i];int ji;while(jbegin a[j-1]tmp){a[j]a[j-1];j--;}a[j]tmp;}}void _MergeSort(vectorint a,int begin,int end,vectorint tmp){if (begin end) {return;}if (end - begin 1 10){InsertSort(a, begin, end);return;}int mid(beginend)/2;_MergeSort(a,begin,mid,tmp);_MergeSort(a,mid1,end,tmp);int begin1begin,end1mid;int begin2mid1,end2end;int ibegin;while(begin1end1begin2end2){if(a[begin1]a[begin2])tmp[i]a[begin1];elsetmp[i]a[begin2];}while(begin1end1)tmp[i]a[begin1];while(begin2end2)tmp[i]a[begin2];for (i begin; i end; i){a[i] tmp[i];}}vectorint sortArray(vectorint nums){vectorint tmp(nums.size());_MergeSort(nums,0,nums.size()-1,tmp);return nums;}
};
八、计数排序 class Solution {
public:vectorint sortArray(vectorint nums){// 找到数组中的最大值和最小值int minVal INT_MAX, maxVal INT_MIN;for (int num : nums) {minVal min(minVal, num);maxVal max(maxVal, num);}// 统计每个元素出现的次数vectorint count(maxVal - minVal 1, 0);for (int num : nums) {count[num - minVal];}// 根据统计结果重新构造排序后的数组vectorint sortedArray;for (int i 0; i count.size(); i) {for (int j 0; j count[i]; j) {sortedArray.push_back(i minVal);}}return sortedArray;}
}; 当我们使用计数排序算法时我们首先需要找到待排序数组中的最大值和最小值。这是为了确定计数数组的大小以及后续构造排序后的数组时的索引范围。接下来我们创建一个计数数组 count其大小为 maxVal - minVal 1其中 maxVal 是数组中的最大值minVal 是数组中的最小值。计数数组用于统计每个元素出现的次数。然后我们遍历待排序数组 nums对于每个元素 num我们将其在计数数组中对应的位置的值加1表示该元素出现了一次。接着我们根据统计结果重新构造排序后的数组 sortedArray。我们从计数数组的第一个位置开始遍历对于每个计数数组的索引 i我们将其对应的值 count[i] 表示的元素值即 i minVal按照出现次数依次添加到 sortedArray 中。最后我们返回排序后的数组 sortedArray。
计数排序算法的时间复杂度为 O(nk)其中 n 是待排序数组的长度k 是待排序元素的范围。由于计数排序是一种稳定的排序算法它可以在线性时间内完成排序。
