给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果。
数据范围: ,数组中每个元素都满足
要求:时间复杂度 ,空间复杂度
进阶:时间复杂度 ,空间复杂度
注:本题数据范围允许绝大部分排序算法,请尝试多种排序算法的实现。
[5,2,3,1,4]
[1,2,3,4,5]
[5,1,6,2,5]
[1,2,5,5,6]
class Solution: def partition(self, arr, l, r) -> int: base = arr[l] pre = l cur = l + 1 while cur <= r: if arr[cur] < base: pre += 1 arr[pre], arr[cur] = arr[cur], arr[pre] cur += 1 arr[l], arr[pre] = arr[pre], arr[l] return pre def inner_sort(self, arr, l, r): if l >= r: return arr mid = self.partition(arr, l, r) self.inner_sort(arr, l, mid - 1) self.inner_sort(arr, mid + 1, r) return arr def MySort(self , arr: List[int]) -> List[int]: # write code here return self.inner_sort(arr, 0, len(arr) - 1)由于是递归调用,最终不能通过:
def inner_sort(self, arr, l, r): if l >= r: return arr tasks = [(l, r)] while tasks: s, e = tasks.pop(0) if s >= e: continue mid = self.partition(arr, s, e) tasks.append((s, mid - 1)) tasks.append((mid + 1, e)) return arr运行通过。
class HeapSort { public: void operator() (vector<int> &nums) { for (int i = nums.size() / 2 - 1; i >= 0; --i) { adjustHeap(nums, i, nums.size()); } for (int j = nums.size() - 1; j >= 0; --j) { swap(nums[0], nums[j]); adjustHeap(nums, 0, j); } } void adjustHeap(vector<int> &nums, int i, int len) { int k = 2 * i + 1; while (k < len) { if (k + 1 < len && nums[k + 1] > nums[k]) { ++k; } if (nums[k] > nums[i]) { swap(nums[k], nums[i]); i = k; k = 2 * i + 1; } else { break; } } } }; class MergeSort { public: void operator()(vector<int> &nums) { mergeSort(nums, 0, nums.size() - 1); } void mergeSort(vector<int> &nums, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } void merge(vector<int> &nums, int left, int mid, int right) { vector<int> aux(right - left + 1, 0); int k = 0, i = left, j = mid + 1; while (i <= mid && j <= right) { if (nums[i] < nums[j]) { aux[k++] = nums[i++]; } else { aux[k++] = nums[j++]; } } while (i <= mid) { aux[k++] = nums[i++]; } while (j <= right) { aux[k++] = nums[j++]; } copy(aux.begin(), aux.end(), nums.begin() + left); } }; class QuickSort { public: void operator()(vector<int> &nums) { quickSort(nums, 0, nums.size() - 1); } void quickSort(vector<int> &nums, int left, int right) { if (left >= right) return; int mid = partition(nums, left, right); quickSort(nums, left, mid); quickSort(nums, mid + 1, right); } int partition(vector<int> &nums, int left, int right) { int pivot = nums[left]; while (left < right) { while (left < right && pivot <= nums[right]) --right; nums[left] = nums[right]; while (left < right && nums[left] <= pivot) ++left; nums[right] = nums[left]; } nums[left] = pivot; return left; } }; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 * @return int整型vector */ vector<int> MySort(vector<int>& arr) { // write code here // HeapSort()(arr); // MergeSort()(arr); QuickSort()(arr); return arr; } };
class Solution { public: vector<int> MySort(vector<int>& arr) { if (arr.size() <= 1) { return arr; } vector<int>::iterator i = arr.begin(); vector<int>::iterator j = arr.begin(); //第一种写法,泡从数组的最左侧开始堆积,向右延伸,而小循环因此就要从数组的右侧向左侧循环。 //此时每一轮会找到一个最小的数,放在左侧。 for (i=arr.begin();i<arr.end()-1;i++) { for (j = arr.end() - 1; j >i; j--) { if (*j < *(j-1) ) { swap<int>(*j, *(j - 1)); } } } //第二种写法,泡从数组的最右侧开始堆积,向左延伸,而小循环因此就要从数组的左侧向右侧循环。 //此时每一轮会找到一个最大的数,放在右侧。 for (i = arr.end()-1; i > arr.begin(); i--) { for (j = arr.begin(); j < i; j++) { if (*j < *(j+1) ) { swap<int>(*j, *(j + 1)); } } } return arr; } };选择排序
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 * @return int整型vector */ vector<int> MySort(vector<int>& arr) { // write code here if(arr.size()<=1) { return arr; } for(auto i=arr.begin();i<arr.end()-1;i++) { auto minIt=i; for(auto j=i;j<=arr.end()-1;j++) { if(*minIt>*j){ minIt=j; } } swap<int>(*i,*minIt); } return arr; } };插入排序
vector<int> MySort(vector<int>& arr) { // write code here if (arr.size() <= 1) { return arr; } //i的左边全都是有序序列 for (auto i = arr.begin() + 1; i <= arr.end() - 1; i++) { int currentNumber = *i; auto j = i; for (; j > arr.begin(); j--) { if (currentNumber < *(j - 1)) { *j = *(j - 1); } else { break; } } *j = currentNumber; //*j=*i; } return arr; }希尔排序:
vector<int> MySort(vector<int>& arr) { // write code here if (arr.size() <= 1) { return arr; } //gap为多少,便是划分为了多少个局部排序小组。 //第一层循环,让gap不断减半的最外层循环。 for(int gap=arr.size()/2;gap>=1;gap/=2){ //内层循环,即插入排序。 //从第一个元素开始直接向上遍历整个数组,遇到每个元素时能自动 //匹配它所在的局部排序小组。 for(int point=gap;point<arr.size();point++) { int keyCard=arr[point]; int j=point-gap; while(keyCard<arr[j]) { arr[j+gap]=arr[j]; j-=gap; if(j<0) break; } arr[j+gap]=keyCard; } } return arr; }归并排序
vector<int> Merge(vector<int>& arr, int front, int mid, int end) { vector<int>leftarr(arr.begin() + front, arr.begin() + mid + 1); vector<int>rightarr(arr.begin() + mid + 1, arr.begin() + end + 1); leftarr.insert(leftarr.end(), numeric_limits<int>::max()); rightarr.insert(rightarr.end(), numeric_limits<int>::max()); int pointLeft =0, pointRight = 0; for (int i = front; i <= end; i++) { if (leftarr[pointLeft] < rightarr[pointRight]) { *(arr.begin() + i) = leftarr[pointLeft]; pointLeft++; } else { *(arr.begin() + i) = rightarr[pointRight]; pointRight++; } } leftarr.clear(); rightarr.clear(); return arr; } vector<int> MergeSort(vector<int>& arr, int front, int end) { if (front >= end) return arr; int mid = (front + end) / 2; MergeSort(arr, front, mid); MergeSort(arr, mid + 1, end); Merge(arr, front, mid, end); return arr; } vector<int> MySort(vector<int>& arr) { // write code here if (arr.size() <= 1) { return arr; } MergeSort(arr, 0,arr.size()-1); return arr; }快速排序:详见代码注释。
//对数组重新排序,使左侧的数小于基数,右侧的数大于基数。 int quick(vector<int>& arr,int low,int high){ int pivot=low; int pivotNumber=arr[pivot]; //如果使用swap来交换的话,赋值操作的次数为3n次 //而使用这种方式来进行交换,赋值操作的次数仅为n+1次。 while(low<high){ while(low<high && arr[high]>pivotNumber){ high--; } arr[low]=arr[high]; while(low<high && arr[low]<pivotNumber){ low++; } arr[high]=arr[low]; } arr[low]=pivotNumber; return low; } vector<int> QuickSort(vector<int>& arr,int begin,int end) { //边界条件为新的子数组长度要大于1. if(begin>=end || begin>=arr.size() || end>=arr.size()) return arr; //取基数进行排序。 int pivot=quick(arr,begin,end); //对排了一次序后的数组,取基数左右两侧再递归地进行排序。 QuickSort(arr,begin,pivot); QuickSort(arr,pivot+1,end); return arr; } vector<int> MySort(vector<int>& arr) { // write code here int length=arr.size(); QuickSort(arr,0,arr.size()-1); return arr; }堆排序:
//版本1.传统写法。 vector<int> AdjustHeap(vector<int>& arr,int begin,int end) { //让两个子节点与父节点比较,如果子节点更大就让它和父节点交换,否则不动。 //因为堆是完全二叉树,所以若父节点的序号是n,那么子节点的序号便是2n+1 int dad=begin; int child=begin*2+1; while(child<=end) { //如果存在右孩子 if (child+1<=end) { //如果两个孩子中右孩子更大 if(arr[child]<arr[child+1]) { child++; } } //如果两个孩子中有个孩子比父亲更大,则交换。 if(arr[child]>arr[dad]) { swap<int>(arr[child],arr[dad]); //继续比较孙辈。 dad=child; child=child*2+1; }else { //说明此处节点往下的节点都满足了大根堆的定义,无需继续向下了。 return arr; } } return arr; } vector<int> HeapSort(vector<int>& arr) { int arrlength=arr.size(); if(arrlength<=1) return arr; //初始化,从最小的一排父节点开始。最后一个父节点(非叶节点)在数组中的 //序号是length/2 - 1,对于非满二叉树来说,次层的叶节点不用管。 for(int i=arrlength/2-1;i>=0;i--) { AdjustHeap(arr,i,arrlength-1); } //完成初始化后,交换堆中的第一个与最后一个元素,并剔除最后一个元素 //然后重新调整整个堆,使其重新符合堆的定义。 for(int i=arrlength-1;i>0;i--) { swap<int>(arr[0],arr[i]); AdjustHeap(arr,0,i-1); } return arr; } //从题解中看的版本2,利用了优先队列。 void heapSort(vector<int> &arr) { priority_queue<int,vector<int>,greater<int>> 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(); } } vector<int> MySort(vector<int>& arr) { // write code here HeapSort(arr); return arr; }计数排序:(内存超过限制,无法排浮点数)
vector<int> CounterSort(vector<int>& arr) { if(arr.size()<=1) { return arr; } int max=arr[0]; int min=arr[0]; //找出最大最小值。 for(int i=0;i<arr.size();i++) { if(arr[i]>max) max=arr[i]; if(arr[i]<min) min=arr[i]; } //对计数器初始化,统计数组中每个数各有多少个 int counterSize=max-min+1; vector<int>counter(counterSize); int index=0; for(int i=0;i<arr.size();i++) { //比如最小值是2,现在的值为3,那么就该放到第2个计数器中去,index为1 index=arr[i]-min; counter[index]++; } //将计数器中的数字弹出来。 index=0; for(int i=0;i<arr.size();i++) { while(counter[index]==0) { index++; } arr[i]=index+min; counter[index]--; } return arr; }桶排序:感觉好像没啥人写桶排序啊……翻了几页都翻不到一份。我贡献一份C++的桶排序好了。
//抄来的堆排序,用于桶内排序。 void heapSort(vector<int> &arr) { priority_queue<int,vector<int>,greater<int> > 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(); } } vector<int> BucketSort(vector<int>& arr) { int max=*max_element(arr.begin(),arr.end()); int min=*min_element(arr.begin(),arr.end()); //找出绝对值最大值。 int power=(int)log2(max); //建桶,注意power要加1。这里坑了我好久。 //因为我们是希望桶的个数是从幂=0~n的,即一共要n+1个桶。 vector<vector<int> >Buckets(power+1); /*for(int i=0;i<=power;i++) { Buckets[i]=new (vector<int>); } */ for(int i=0;i<arr.size();i++) { //确定每个数的大小应该归属于哪个桶,并塞进去。 int currentPower=(int)log2(arr[i]); Buckets[currentPower].push_back(arr[i]); } //用于把桶中的东西倒回去的指针,指示现在倒到哪了。 int index=0; for(auto bucket:Buckets) { heapSort(bucket); for(auto j:bucket) { arr[index++]=j; } } return arr; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here // 冒泡排序 return bubbleSort(arr); } //优化过的冒泡排序 private int[] bubbleSort(int[] array){ int position = array.length - 1; /*外循环为排序趟数,array.length个数进行array.length-1趟 */ for(int i = 0;i<array.length-1;i++){ boolean isSwap = false; /*用来记录最后一次交换的位置*/ int newPosition = 0; /*内循环为每趟比较的次数,第i趟比较array.length-i次 */ for(int j = 0;j<position;j++){ /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */ if(array[j]>array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSwap = true; /*记录最后一次交换的位置*/ newPosition = j; } /*查看每趟比较后的数组元素*/ // System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:"); // for(int k = 0;k<array.length;k++){ // System.out.print(array[k]+" "); // } // System.out.println(); } /*如果没有交换过元素,则已经有序,不再进行接下来的比较*/ if(!isSwap){ break; } /*下趟比较所需要比较到的位置*/ position = newPosition; } return array; } }
public int[] MySort (int[] arr) { // write code here trueMergeSort(arr,new int[arr.length],0,arr.length-1); return arr; } public static void trueMergeSort(int[] arr,int[] tempArr,int left,int right){ if(left >= right){ return; } int mid = (left+right)/2; trueMergeSort(arr,tempArr,left,mid); trueMergeSort(arr,tempArr,mid+1,right); partitionMerge(arr,tempArr,left,right); } public static void partitionMerge(int[] arr,int[] tempArr,int left,int right){ int mid = (left + right)>>>1; int lPointer = left,rPointer = mid+1,tempIndex = left; while(lPointer<=mid && rPointer<=right){ tempArr[tempIndex++] = arr[lPointer]>arr[rPointer]? arr[rPointer++]:arr[lPointer++]; } while(lPointer<=mid){ tempArr[tempIndex++]=arr[lPointer++]; } while(rPointer<=right){ tempArr[tempIndex++]=arr[rPointer++]; } for(int i=left;i<=right;i++){ arr[i] = tempArr[i]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here sort(arr); return arr; } public static void sort(int []arr){ //1.构建大顶堆 for(int i=arr.length/2-1;i>=0;i--){ //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 adjustHeap(arr,0,j);//重新对堆进行调整 } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上) * @param arr * @param i * @param length */ public static void adjustHeap(int []arr,int i,int length){ int temp = arr[i];//先取出当前元素i for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始 if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点 k++; } if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) arr[i] = arr[k]; i = k; }else{ break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * @param arr * @param a * @param b */ public static void swap(int []arr,int a ,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
class Solution { public: vector<int> MySort(vector<int>& arr) { if(arr.size() == 0) return {}; quicksort(arr, 0, arr.size()-1); return arr; } int partition(vector<int>& arr, int left, int right) { // 取数组中最右边的值为主元 int count = left; // 记录小于主元的个数 while(left < right) { if(arr[left] < arr[right]) { swap(arr[left], arr[count]); ++count; } ++left; } swap(arr[count], arr[right]); return count; } void quicksort(vector<int>& arr, int left, int right) { if(left > right) // 递归结束条件 return ; int privotIndex = partition(arr, left, right); quicksort(arr, left, privotIndex-1); quicksort(arr, privotIndex+1, right); } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here if(arr.length==0) return arr; PriorityQueue<Integer> pq=new PriorityQueue<>(); int[] ans=new int[arr.length]; for(int i=0;i<arr.length;i++){ pq.offer(arr[i]); } for(int i=0;i<arr.length;i++){ ans[i]=pq.poll(); } // while(!pq.isEmpty()) return ans; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { sort(arr, 0, arr.length - 1); return arr; } public void sort(int[] a, int low, int high) { // 递归终止条件 if(low >= high) { return; } int i = low; int j = high; // 基准位 int temp = a[low]; while(i < j) { // 找出从右到左第一个小于基准位的数下标 while(i < j && temp <= a[j]) { j--; } // 找出从左到右第一个大于基准位的数下标 while(i < j && temp >= a[i]) { i++; } if(i < j) { swap(a, i, j); } } // 此时 i==j swap(a, low, i); sort(a, low, i-1); sort(a, i+1, high); } public void swap(int[] a, int i, int j) { int c = a[i]; a[i] = a[j]; a[j] = c; } }
//简单明了的java代码 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here quickSort(arr,0,arr.length-1); return arr; } public void quickSort(int[] arr, int left, int right) { int left_copy = left; int right_copy = right; int ken = arr[left];//每次取数组的最左作为基准数 int flag = 0; // 填坑:0表示坑在左边,1表示坑在右边 while (left < right) { if (flag == 0) { if (ken > arr[right]) { arr[left] = arr[right]; left++; flag = 1;//坑换到右边 } else if (ken <= arr[right]) { right --; } } else if (flag == 1) { if (ken < arr[left]) { arr[right] = arr[left]; right--; flag = 0;//坑换到左边 } else if (ken >= arr[left]) { left ++; } } } arr[left] = ken;//把基准数填在最后左右见面的位置 if (left_copy < left-1) quickSort(arr, left_copy, left-1); if (left + 1 < right_copy) quickSort(arr, left+1, right_copy); } }
/** * 使用sort函数 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ function MySort( arr ) { return arr.sort((a,b)=>a-b) } module.exports = { MySort : MySort };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 * @return int整型vector */ vector<int> MySort(vector<int>& arr) { // write code here mySort1(arr); return arr; } // 1、快速排序(通过) // 时间复杂度O(logn)。空间复杂度是O(n)。 // 主要是要找出标杆值(中间值),默认最后一个值为标杆值,然后比它小的放左边,比他大的放右边,然后交换最后一位。就得到标杆值在中间的下标。 // 树,从上往下排序 // 不稳定算法 void mySort1(vector<int>& arr) { quicksort(arr, 0, arr.size()-1); } void quicksort(vector<int> &arr, int left, int right) { if (left > right) return; int pivotIndex = partition(arr, left, right); // 标杆值所在的位置 quicksort(arr, left, pivotIndex-1); // 左半边 quicksort(arr, pivotIndex+1, right); // 右半边 } // 这里只需要把数据归类就行,不需要比较大小;每次比标杆值小的放左边,比标杆值大的放右边。 int partition(vector<int> &arr, int left, int right) { // 最后一个值当做标杆(自己随意定) int mark = arr[right]; // 记录小于标杆值的个数 int counter = left; for (int i = left; i < right; i++) { if (arr[i] < mark) { // 当前值和标杆值比较,决定是放在左边还是右边 swap(arr[i], arr[counter++]); } } swap(arr[counter], arr[right]); // 最后把标杆值移到中间位置,然后返回下标。 return counter; } // 2、归并排序(通过) // 时间复杂度O(logn)。空间复杂度是O(n)。 // 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 // 树,从下往上排序 // 是稳定的算法 void mySort2(vector<int>& arr) { mergeSort(arr, 0, arr.size()-1); } void mergeSort(vector<int> &arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); // 递归 左半边 mergeSort(arr, mid+1, right); // 递归 右半边 merge(arr, left, mid, right); // 合并两个有序的数组(参考合并两个有序的链表) } // 合并两个有序数组 void merge(vector<int> &arr, int left, int mid, int right) { vector<int> tmp(right-left+1); // 开辟新的数组 int i = left, j = mid+1, 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(vector<int> &arr) { priority_queue<int,vector<int>,greater<int>> 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(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr.size()-i-1; j++) { if (arr[j]>arr[j+1]) { swap(arr[j], arr[j+1]); } } } } // 5、选择排序(超时) // 时间复杂度O(n2),空间复杂度O(1) // 从前往后排 // 遍历数组,找出最小值,最小的放在前面,不稳定排序 void selectionSort(vector<int>& arr) { int minIndex = 0; for (int i = 0; i < arr.size(); i++) { minIndex = i; for (int j = i+1; j < arr.size(); j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr[i], arr[minIndex]); } } // 6、插入排序(超时) // 时间复杂度O(n2),空间复杂度O(1) // 从前往后排 // 遍历数组,找出一个值,往排好的数组里面插入合适的位置。稳定排序 void insetionSort(vector<int>& 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[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = currentVal; } } };
class Solution: def MySort(self , arr ): # write code here # return self.bubble_sort(arr) # return self.select_sort(arr) # return self.insert_sort(arr) return self.quick_sort(arr) # return self.merge_sort(arr) def bubble_sort(self, arr): # 冒泡排序 不通过 for i in range(len(arr) - 1): for j in range(len(arr) - i - 1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr def select_sort(self, arr): # 选择排序 不通过 for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[j] < arr[min_index]: min_index = j arr[min_index], arr[i] = arr[i], arr[min_index] return arr def insert_sort(self, li): # 插入排序 不通过 for i in range(1, len(li)): tmp = li[i] # tmp要插入的之 j = i - 1 while j >= 0 and li[j] > tmp: # 前面的值比tmp大 li[j+1] = li[j] # 前面的值向后移一位 j = j - 1 # 继续向前对比 li[j+1] = tmp # 直到while不满足条件, 也就是前面的值比tmp小, 插入到比tmp小的值后 return li def quick_sort(self, li): # 快速排序 通过 if len(li) < 2: return li else: tmp = li[0] less = [i for i in li[1:] if i <= tmp] more = [i for i in li[1:] if i > tmp] return self.quick_sort(less) + [tmp] + self.quick_sort(more) def merge_sort(self, li): # 归并排序 可能通过 可能不通过 if len(li) < 2: return li else: num = len(li) // 2 left = self.merge_sort(li[:num]) right = self.merge_sort(li[num:]) return self.merge(left, right) def merge(self, left, right): l,r = 0,0 result = [] while l < len(left) and r < len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += left[l:] result += right[r:] return result
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @param arrLen int arr数组长度 * @return int整型一维数组 * @return int* returnSize 返回数组行数 */ #include<stdio.h> void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // 冒泡排序会超时 void BuubleSort(int* arr, int arrlen) { for (int i = 0; i < arrlen; i++) { for (int j = 1; j < arrlen; j++) { if (arr[j - 1] > arr[j]) { Swap(&arr[j - 1], &arr[j]); } } } } // 选择排序超时 void SelectSort(int* arr, int arrlen) { int begin = 0; int end = arrlen - 1; while (begin <= end) { int maxi = begin; int mini = begin; for (int i = begin; i <= end; i++) { if (arr[i] > arr[maxi]) { maxi = i; } if (arr[i] < arr[mini]) { mini = i; } } Swap(&arr[begin], &arr[mini]); if (maxi == begin) { maxi = mini; } Swap(&arr[maxi], &arr[end]); end--; begin++; } } //插入排序 (可以通过) void InsertSort(int* arr, int arrlen) { for (int i = 0; i < arrlen - 1; i++) { int end = i; int key = arr[end + 1]; /*while (end >= 0) { while (arr[end] > key) { arr[end + 1] = arr[end]; end--; } arr[end + 1] = key; break; } */ while (end >= 0) { if (arr[end] > key) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = key; } } //希尔排序通过 void ShellSort(int* arr, int arrLen) { int gap = arrLen; while (gap > 1) { gap = gap / 2; for (int i = 0; i < arrLen - gap; i++) { int end = i; int key = arr[end + gap]; while (end >= 0) { if (arr[end] > key) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = key; } } } //挖坑法的快速排序 int PartSort(int* arr, int left, int right) { int pvoit = left; int key = arr[pvoit]; while (left < right) { while (left < right && arr[right] >= key) { right--; } arr[pvoit] = arr[right]; pvoit = right; while (left < right && arr[left] <= key) { left++; } arr[pvoit] = arr[left]; pvoit = left; } arr[pvoit] = key; return pvoit; } void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } int pvoit = PartSort(arr, left, right); QuickSort(arr, left, pvoit - 1); QuickSort(arr, pvoit + 1, right); } //归并排序 void _MergeSort(int* arr, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) >> 1; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid + 1, right, tmp); int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int index = left; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { tmp[index++] = arr[begin1++]; } else { tmp[index++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[index++] = arr[begin1++]; } while (begin2 <= end2) { tmp[index++] = arr[begin2++]; } for (int i = left; i <= right; i++) { arr[i] = tmp[i]; } } void MergeSort(int* arr, int left, int right) { int* tmp = (int*)malloc(sizeof(int) * (right - left + 1)); _MergeSort(arr, left, right, tmp); free(tmp); tmp = NULL; } void AdjustDwon(int* arr, int arrLen, int root) { int parent = root; int child = parent * 2 + 1;//默认是左孩子 while (child < arrLen) { if (child + 1 < arrLen && arr[child + 1] > arr[child]) { child += 1; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* arr, int arrLen) { //建堆 for (int i = (arrLen - 1 - 1) / 2; i >= 0; i--) { AdjustDwon(arr, arrLen, i); } int end = arrLen - 1; while (end > 0) { Swap(&arr[0], &arr[end]); AdjustDwon(arr, end, 0); end--; } } int* MySort(int* arr, int arrLen, int* returnSize) { // write code here //BuubleSort(arr, arrLen); //SelectSort(arr, arrLen); //InsertSort(arr, arrLen); //ShellSort(arr, arrLen); //MergeSort(arr, 0, arrLen - 1); //HeapSort(arr, arrLen); QuickSort(arr, 0,arrLen - 1); *returnSize = arrLen; return arr; }七大排序:冒泡和选择超时,插入排序。希尔排序。快速排序。归并排序。堆排序
//此代码适用于像我这样的萌新小白们,直接使用数组自带的sort方法排序,代码简洁可读性高, //缺点就是运行时间长,在大佬眼里的破代码哈哈哈。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here if(arr==null){ return null; } if(arr!=null){ Arrays.sort(arr); } return arr; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ public int[] MySort (int[] arr) { // write code here // 快速排序,时间复杂度O(N*logN),空间复杂度O(logN),不稳定 quickSort(arr, 0, arr.length - 1); // 归并排序,时间复杂度O(N*logN),空间复杂度O(N),稳定 // mergeSort(arr); // 堆排序(大根堆),时间复杂度O(N*logN),空间复杂度O(N),不稳定 // heapSort(arr); // 希尔排序,时间复杂度O(N*logN),空间复杂度O(1),不稳定 // shellSort(arr); // 基数排序,时间复杂度O(C*N),C为2*(数值长度+1),空间复杂度O(K+N),K为数值长度,稳定 // baseSort(arr); return arr; } private void quickSort (int[] arr, int left, int right) { if (left < right) { int idx = partition(arr, left, right); quickSort(arr, left, idx - 1); quickSort(arr, idx + 1, right); } } private int partition (int[] arr, int left, int right) { int mark = arr[left]; while (left < right) { while (left < right && arr[right] >= mark) { right--; } if (left < right) { arr[left++] = arr[right]; } while (left < right && arr[left] <= mark) { left++; } if (left < right) { arr[right--] = arr[left]; } } arr[left] = mark; return left; } private void mergeSort (int[] arr) { int[] tmp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, tmp); } private void mergeSort (int[] arr, int left, int right, int[] tmp) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid, tmp); mergeSort(arr, mid + 1, right, tmp); merge(arr, left, right, tmp); } } private void merge(int[] arr, int left, int right, int[] tmp) { int mid = left + (right - left) / 2, i = left, j = mid + 1, k = 0; 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++]; } k = 0; while (left <= right) { arr[left++] = tmp[k++]; } } private void heapSort (int[] arr) { int len = arr.length, buildMaxHeapLoopLimit = arr.length / 2; for (int i = buildMaxHeapLoopLimit; i >= 0; i--) { heapify(arr, i, len); } for (int i = len - 1; i > 0; i--) { swap(arr, i, 0); len--; heapify(arr, 0, len); } } private void heapify (int[] arr, int cur, int len) { int left = 2 * cur + 1, right = 2 * cur + 2, maxIdx = cur; if (left < len && arr[left] > arr[maxIdx]) { maxIdx = left; } if (right < len && arr[right] > arr[maxIdx]) { maxIdx = right; } if (cur != maxIdx) { swap(arr, cur, maxIdx); heapify(arr, maxIdx, len); } } private void shellSort(int[] arr) { for (int step = arr.length / 2; step >= 1; step /= 2) { for (int i = step, tmp, j; i < arr.length; i++) { tmp = arr[i]; j = i - step; while (j >= 0 && arr[j] > tmp) { arr[j + step] = arr[j]; j -= step; } arr[j + step] = tmp; } } } private void baseSort (int[] arr) { List<List<Integer>> bucketList = new ArrayList<>(); // 建立0-9,共10个桶 int baseCount = 10, numSize = 10; for (int i = 0; i < baseCount; i++) { bucketList.add(new ArrayList<>()); } for (int i = 0; i < numSize; i++) { for (int num : arr) { bucketList.get(getBaseNum(num, i)).add(num); } int j = 0; for (List<Integer> bucket : bucketList) { for (Integer num : bucket) { arr[j++] = num; } bucket.clear(); } } // 负数的存在,需使用正/负数桶 List<Integer> posBucket = bucketList.get(0), negBucket = bucketList.get(1); for (int num : arr) { if (num > 0) { posBucket.add(num); } else { negBucket.add(num); } } int idx = 0; for (int i = negBucket.size() - 1; i >= 0; i--) { arr[idx++] = negBucket.get(i); } for (Integer num : posBucket) { arr[idx++] = num; } } private int getBaseNum (int val, int count) { val = Math.abs(val); for (int i = 0; i < count; i++) { val /= 10; } return val %= 10; } private void swap (int[] arr, int x, int y) { int tmp = arr[x]; arr[x] = arr[y]; arr[y] = tmp; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 * @return int整型vector */ vector<int> MySort(vector<int>& arr) { // write code here quickSort(arr, 0, arr.size()-1); return arr; } void quickSort(vector<int>& arr,int low,int high){ int mid = partition(arr, low, high); if(low<mid-1) quickSort(arr, low, mid-1); if(mid+1<high) quickSort(arr, mid+1, high); } int partition(vector<int>& arr,int low,int high){ int base = arr[low]; while(low<high){ while(low<high&&arr[high]>=base) high--; arr[low] = arr[high]; while(low<high&&arr[low]<=base) low++; arr[high] = arr[low]; } arr[low] = base; return low; } };