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

题目描述

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

示例 1：

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

  

 

  
1
  
2
 

示例 2：

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

  

 

  
1
  
2
 

提示：

• 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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

运行结果

提交代码（冒泡排序）

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

运行结果

提交代码（插入排序 基于插入）

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

运行结果

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

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

运行结果

提交代码（归并）

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

运行结果

提交代码（快排）

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; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

运行结果

题目来源

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

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108955005