一.面试手撕原题的题目排序逻辑是 输入一个数组和一个kk0就是降序k1就是升序。class Solution { public: vectorint sortArray(vectorint nums, int k) { int n nums.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { // 根据 k 决定比较方向 bool needSwap (k 1) ? (nums[j] nums[j 1]) : (nums[j] nums[j 1]); if (needSwap) { swap(nums[j], nums[j 1]); swapped true; } } if (!swapped) break; // 没有交换则已经有序 } return nums; } };1.冒泡排序 O(n^2)class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { if (nums[j] nums[j 1]) { swap(nums[j], nums[j 1]); swapped true; } } if (!swapped) break; } return nums; } };2.快速排序class Solution { public: vectorint sortArray(vectorint nums) { quicksort(nums,0,nums.size()-1); return nums; } void quicksort(vectorint nums,int left,int right){ if(leftright) return; int ppivotnum(nums,left,right); quicksort(nums,left,p-1); quicksort(nums,p1,right); } int pivotnum(vectorint nums,int left,int right){ int randIdx left rand() % (right - left 1); swap(nums[randIdx], nums[right]); int anums[right]; int ileft; for(int jleft;jright;j){ if(nums[j]a){ swap(nums[i],nums[j]); i; } } swap(nums[i],nums[right]); return i; } };
