# LeetCode 912. 排序数组（10种排序）

## 1. 题目

```示例 1：

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

## 2. 解题

### 2.1 插入排序

```class Solution {
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j;
for(i = 0; i < arr.size(); ++i)
{
for(j = i; j > 0; --j)
{
if(arr[j-1] > arr[j])
swap(arr[j-1],arr[j]);
else
break;
}
}
return arr;
}
};```

9 / 10 个通过测试用例，超时

### 2.2 冒泡排序

```class Solution {
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j;
bool arrSorted = false;
for(i = 0; i < arr.size(); ++i)
{
arrSorted = true;
for(j = 1; j <= arr.size()-1-i; ++j)
{
if(arr[j-1] > arr[j])
{
swap(arr[j-1],arr[j]);
arrSorted = false;
}
}
if(arrSorted)
break;
}
return arr;
}
};```

### 2.3 选择排序

```class Solution {	//选择
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j, minIdx = 0;
for(i = 0; i < arr.size()-1; ++i)
{
minIdx = i;
for(j = i+1; j < arr.size(); ++j)
{
if(arr[minIdx] > arr[j])
minIdx = j;
}
swap(arr[i],arr[minIdx]);
}
return arr;
}
};```

### 2.4 希尔排序

```class Solution {	//希尔
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j, gap = 1;
for(gap = arr.size()/2; gap > 0; gap /= 2)
{
for(i = gap; i < arr.size(); ++i)
{
for(j = i; j-gap >= 0 && arr[j-gap]>arr[j]; j -= gap)
swap(arr[j-gap],arr[j]);
}
}
return arr;
}
};```

72 ms 15.8 MB

### 2.5 归并排序

```class Solution {	//归并
vector<int> temp;
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
temp.resize(arr.size());
mergeSort(arr,0, arr.size()-1);
return arr;
}

void mergeSort(vector<int>& arr, int l, int r)
{
if(l == r)
return;
int mid = l+((r-l)>>1);
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}

void merge(vector<int>& arr, int l, int mid, int r)
{
int i = l, j = mid+1, k = 0;
while(i <= mid && j <= r)
{
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i <= mid)
temp[k++] = arr[i++];
while(j <= r)
temp[k++] = arr[j++];
for(k = 0, i = l; i <= r; ++i,++k)
arr[i] = temp[k];
}
};```

52 ms 16 MB

### 2.6 快速排序

```class Solution {	//快排
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
qsort(arr,0, arr.size()-1);
return arr;
}

void qsort(vector<int>& arr, int l, int r)
{
if(l >= r)
return;
int Pl = l, Pr = l;
partition(arr,l,r,Pl,Pr);
qsort(arr,l,Pl-1);
qsort(arr,Pr+1,r);
}

void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr)
{
selectMid(arr,l,r);
int P = arr[l];
int i = l, j = r;
while(i < j)
{
while(i < j && P < arr[j])//没有等于号，哨兵都在左侧
j--;
swap(arr[i], arr[j]);
while(i < j && arr[i] <= P)
i++;
swap(arr[i], arr[j]);
}
Pl = Pr = i;
for(i = i-1; i >= l; --i)//聚集左侧与哨兵相等的到中间
{
if(arr[i] == P)
{
Pl--;
swap(arr[i], arr[Pl]);
}
}
}

void selectMid(vector<int>& arr, int l, int r)
{
int mid = l+((r-l)>>1);
if(arr[mid] > arr[r])
swap(arr[mid],arr[r]);
if(arr[l] > arr[r])
swap(arr[l], arr[r]);
if(arr[mid] > arr[l])
swap(arr[mid], arr[l]);
}
};```

52 ms 15.6 MB 96 ms 15.8 MB（删除聚集哨兵操作后的用时）

### 2.7 堆排序

```class Solution {	//堆排序, 建堆（升序建大堆，降序建小堆）
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
for(int i = arr.size()/2-1; i >= 0; --i)
for(int i = arr.size()-1; i >= 0; --i)
{
swap(arr[i],arr[0]);
}
return arr;
}

void adjust(vector<int>& arr, int i, int len)
{
int lchild = 2*i+1, rchild = 2*i+2, maxIdx = i;
while(lchild < len)
{
if(lchild < len && arr[lchild] > arr[maxIdx])
maxIdx = lchild;
if(rchild < len && arr[rchild] > arr[maxIdx])
maxIdx = rchild;
if(maxIdx != i)
{
swap(arr[i],arr[maxIdx]);
lchild = 2*maxIdx+1;
rchild = lchild+1;
i = maxIdx;
}
else
break;
}
}
};```

72 ms 15.8 MB

### 2.8 计数排序

```class Solution {	//计数排序
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j = 0, min, max;
min = max = arr[0];
for(i = 1; i < arr.size(); ++i)
{
min = arr[i] < min ? arr[i] : min;
max = arr[i] > max ? arr[i] : max;
}
const int N = max-min+1;
vector<int> count(N,0);
for(i = 0; i < arr.size(); ++i)
count[arr[i]-min]++;
for(i = 0; i < N; ++i)
{
while(count[i]--)
arr[j++] = i+min;
}
return arr;
}
};```

36 ms 16.1 MB

### 2.9 桶排序

• 数据装桶，桶内快排
```class Solution {	//桶排序
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, j = 0, min, max;
min = max = arr[0];
for(i = 1; i < arr.size(); ++i)
{
min = arr[i] < min ? arr[i] : min;
max = arr[i] > max ? arr[i] : max;
}
if(min == max)
return arr;
int div = 1000;//桶个数
int space = (max-min)/div+1;
vector<int> temp(arr.size());
vector<int> bucketsize(div,0);
vector<int> bucketPos(div,0);
for(i = 0; i < arr.size(); ++i)
bucketsize[(arr[i]-min)/space]++;
bucketPos[0] = bucketsize[0];
for(i = 1; i < div; ++i)
bucketPos[i] += bucketPos[i-1] + bucketsize[i];//桶结束位置的下一个
for(i = 0; i < arr.size(); ++i)
temp[--bucketPos[(arr[i]-min)/space]] = arr[i];
for(i = 0; i < div; ++i)
{
if(bucketsize[i] > 1)
{
qsort(temp,bucketPos[i],bucketPos[i]+bucketsize[i]-1);
}
}
for(i = 0; i < arr.size(); ++i)
arr[i] = temp[i];
return arr;
}

void qsort(vector<int>& arr, int l, int r)
{
if(l >= r)
return;
int Pl = l, Pr = l;
partition(arr,l,r,Pl,Pr);
qsort(arr,l,Pl-1);
qsort(arr,Pr+1,r);
}

void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr)
{
selectMid(arr,l,r);
int P = arr[l];
int i = l, j = r;
while(i < j)
{
while(i < j && P < arr[j])//没有等于号，哨兵都在左侧
j--;
swap(arr[i], arr[j]);
while(i < j && arr[i] <= P)
i++;
swap(arr[i], arr[j]);
}
Pl = Pr = i;
for(i = i-1; i >= l; --i)
{
if(arr[i] == P)
{
Pl--;
swap(arr[i], arr[Pl]);
}
}
}

void selectMid(vector<int>& arr, int l, int r)
{
int mid = l+((r-l)>>1);
if(arr[mid] > arr[r])
swap(arr[mid],arr[r]);
if(arr[l] > arr[r])
swap(arr[l], arr[r]);
if(arr[mid] > arr[l])
swap(arr[mid], arr[l]);
}
};```

40 ms 16.3 MB

### 2.10 基数排序

• 注意处理负数，被坑了，负数%后越界，window不报错尽然。。
```class Solution {	//基数排序
vector<int> temp;
public:
vector<int> sortArray(vector<int>& arr) {
if(arr.size() <= 1)
return arr;
int i, max = INT_MIN;
long exp;
temp.resize(arr.size());
for(i = 0; i < arr.size(); ++i)
{
arr[i] += 50000;//便于负数处理
max = arr[i] > max ? arr[i] : max;
}
for(exp = 1; max/exp > 0; exp*=10)

for(i = 0; i < arr.size(); ++i)
arr[i] -= 50000;//还原
return arr;
}
{
vector<int> bucketsize(10,0);
int i;
for(i = 0; i < arr.size(); ++i)
bucketsize[(arr[i]/exp)%10]++;
for(i = 1; i < 10; ++i)
bucketsize[i] += bucketsize[i-1];//桶最后一个位置+1
for(i = arr.size()-1; i >= 0; --i)
temp[--bucketsize[(arr[i]/exp)%10]] = arr[i];
for(i = 0; i < arr.size(); ++i)
arr[i] = temp[i];
}
};```

56 ms 16 MB

## 3. 复杂度表

r 为排序数字的范围，d 是数字总位数，k 是数字总个数

0 条评论

• ### LeetCode 1243. 数组变换

首先，给你一个初始数组 arr。然后，每天你都要根据前一天的数组生成一个新的数组。

• ### LeetCode 1502. 判断能否形成等差数列

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

• ### LeetCode 1426. 数元素（哈希set）

给你一个整数数组 arr， 对于元素 x ，只有当 x + 1 也在数组 arr 里时，才能记为 1 个数。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题9-5 通讯录排序

输入n个朋友的信息，包括姓名、生日、电话号码，本题要求编写程序，按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。

• ### JavaScript实现八大内部排序算法

? 注：基数排序中：r是关键字的基数，d是长度，n是关键字的个数 1.插入排序 基本思想：在序号i之前的元素(0到i-1)已经排好序，本趟需要找到i对应的元素...

• ### 快速排序

参考：http://www.cnblogs.com/skywang12345/p/3596746.html  下面上代码： #include<iostream>...

• ### 多图养眼！Partition，荷兰国旗问题与随机快排

Partition的过程：给定一个数组arr，和一个整数num。把小于等于num的数放在数组的左边，大于num的数放在数组的右边。