LeetCode刷题（186）～排序数组【基础排序算法练习：选择｜冒泡｜插入｜归并｜快排】

题目描述

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1] 输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000-50000 <= nums[i] <= 50000

解答 By 海轰

提交代码（选择排序）

vector<int> sortArray(vector<int>& nums) { int len=nums.size(); for(int i=0;i<len-1;++i){ int minIndex=i; for(int j=i+1;j<len;++j){ if(nums[j]<nums[minIndex]){ minIndex=j; } } swap(nums[i],nums[minIndex]); } return nums; }

运行结果 提交代码（冒泡排序）

vector<int> sortArray(vector<int>& nums) { int len=nums.size(); for(int i=len-1;i>=0;--i){ // 每次选出一个最大数 放在第i个位置 bool sorted=true;// 若后面一轮循环没有发生交换 则说明数组本就是有序第 直接返回即可 for(int j=0;j<i;++j){ if(nums[j]>nums[j+1]){ swap(nums[j],nums[j+1]); sorted=false; } } if(sorted) break; } return nums; }

运行结果 提交代码（插入排序 基于插入）

vector<int> sortArray(vector<int>& nums) { int len=nums.size(); for(int i=1;i<len;++i){ for(int j=i;j>0;--j){ if(nums[j-1]>nums[j]){ swap(nums[j-1],nums[j]); } else{ break; } } } return nums; }

运行结果 提交代码（插入排序 基于赋值，其实就是移动元素）

vector<int> sortArray(vector<int>& nums) { int len=nums.size(); for(int i=1;i<len;++i){ int temp=nums[i]; int j=i; while(j>0 && nums[j-1]>temp){ nums[j]=nums[j-1]; --j; } nums[j]=temp; } return nums; }

运行结果 提交代码（归并）

void mergeTwoSortedArray(vector<int>& nums,int left,int mid,int right){ int len=right-left+1; vector<int> temp(len); for(int i=0;i<len;++i){ temp[i]=nums[left+i]; } // 左边数组开始的位置 int l=0; // 右边数组开始的位置 int r=mid-left+1; //下面if else中判断条件顺序得注意 不得轻易调整 for(int i=0;i<len;++i){ if(l>mid-left){ nums[left+i]=temp[r]; r++; } else if(r>len-1){ nums[left+i]=temp[l]; l++; } else if(temp[l]<temp[r]){ nums[left+i]=temp[l]; l++; } else{ nums[left+i]=temp[r]; r++; } } } 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); mergeTwoSortedArray(nums,left,mid,right); } vector<int> sortArray(vector<int>& nums) { mergeSort(nums,0,nums.size()-1); return nums; }

运行结果 提交代码（快排）

void quickSort(vector<int>& nums,int left,int right){ if(left>=right){ return ; } int pIndex=partition(nums,left,right); quickSort(nums,left,pIndex-1); quickSort(nums,pIndex+1,right); } int partition(vector<int>& nums,int left,int right){ int pivot=nums[left]; int lt=left; for(int i=left+1;i<=right;++i){ if(nums[i]<pivot){ ++lt; swap(nums[lt],nums[i]); } } swap(nums[left],nums[lt]); return lt; } vector<int> sortArray(vector<int>& nums) { quickSort(nums,0,nums.size()-1); return nums; }

运行结果

题目来源

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-an-array

海轰Pro 认证博客专家 C/C++ 微信小程序 微信小程序：「海轰Pro」微信公众号：「海轰Pro」知乎：「海轰Pro」微博：「海轰Pro」