1067 lines
20 KiB
Markdown
1067 lines
20 KiB
Markdown
---
|
||
title: "排序合集"
|
||
date: 2022-05-19T10:34:31+08:00
|
||
|
||
---
|
||
|
||
内容参考：[十大经典排序算法](https://sort.hust.cc/)
|
||
|
||
---------------------
|
||
|
||
#### 归并排序
|
||
|
||
基本思想：
|
||
|
||
将待排序元素分为大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合并成为所要求的排好序的集合
|
||
|
||
JAVA实现
|
||
|
||
``` java
|
||
public static void mergeSort(Comparable[]a)
|
||
{
|
||
Comparable []b=new Comparable[a.length];
|
||
int s=1;
|
||
while(s<a.length)
|
||
{
|
||
mergePass(a,b,s);//合并到数组a
|
||
s+=s;
|
||
mergePass(b,a,s);//合并到数组b
|
||
s+=s;
|
||
}
|
||
}
|
||
|
||
public static void mergePass(Comparable []x,Comparable[]y,int s)
|
||
{
|
||
int i =0;
|
||
while(i<=x.length-2*s)
|
||
{
|
||
//合并大小为s的相邻两段子数组
|
||
merge(x,y,i,i+s-1,i+2*s-1);
|
||
i=i+2*s;
|
||
|
||
}
|
||
//剩下的元素个数小于2s时
|
||
if(i+s<x.length)
|
||
merge(x,y,i,i+s-1,x.length-1);
|
||
else
|
||
//剩余元素复制到y
|
||
for(int j=i;j<x.length;j++)
|
||
y[j]=x[j];
|
||
}
|
||
|
||
|
||
public static void merge(Comparable[]c,Comparable[]d,int l,int m,int r)
|
||
{
|
||
//合并c[l:m]和c[m+1:r]到d[l:r]
|
||
int i=l,j=m+l,k=l;
|
||
while((i<=m)&&(j<=r))
|
||
if(c[i].compareTo(c[j])<=0)
|
||
{
|
||
d[k++]=c[i++];
|
||
}
|
||
else
|
||
{
|
||
d[k++]=c[j++];
|
||
}
|
||
if(i>m)
|
||
for(int q=j;q<=r;q++)
|
||
{
|
||
d[k++]=c[q];
|
||
}
|
||
|
||
else
|
||
{
|
||
for(int q=i;q<=m;q++)
|
||
d[k++]=c[q];
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
C++实现
|
||
|
||
```c++
|
||
void merge(vector<int>& arr,int l,int mid,int r)
|
||
{
|
||
int index = 0 ;
|
||
int ptrL = l;
|
||
int ptrR = mid;
|
||
static vector<int>tempary;
|
||
if(arr.size() > tempary.size())
|
||
{
|
||
tempary.resize(arr.size());//更新缓存数组长度
|
||
}
|
||
while(ptrL ! = mid && ptrR ! = r)
|
||
{
|
||
if(arr[ptrL] < arr[ptrR])//比较左右分组后数组长度
|
||
{
|
||
tempary[index++] = arr[ptrL++];
|
||
}
|
||
else
|
||
{
|
||
tempary[index++] = arr[ptrR++];
|
||
}
|
||
}
|
||
while(ptrL ! = mid)
|
||
{
|
||
tempary[index++] = arr[ptrL++];
|
||
}
|
||
while(ptrR ! = r)
|
||
{
|
||
tempary[index++] = arr[ptrR++];
|
||
}
|
||
copy(tempary.begin(),tempary.begin()+index,arr.begin()+l)
|
||
|
||
}
|
||
|
||
void mergeSort(vector<int>& arr,int l,int r)
|
||
{
|
||
if(r - l <= 1>)
|
||
{
|
||
return;
|
||
}
|
||
int mid = ( l + r ) / 2;
|
||
mergeSort(arr,l,mid);
|
||
mergeSort(arr,mid,r);//递归排序
|
||
merge(arr,l,mid,r);//合并数组
|
||
}
|
||
```
|
||
|
||
-----------------------
|
||
|
||
#### 快速排序
|
||
|
||
基本思想
|
||
|
||
对于输入的数组a[p:r]
|
||
1. 分解：以a[p]为基准元素将a[p:r]分为3段a[p:q-1],a[q]和a[q+1:r]
|
||
<br>使得a[p:q-1]中任何元素小于等于a[q]
|
||
<br>a[q+1:r]中任何元素大于等于a[q]
|
||
|
||
2. 递归求解：通过递归调用排序算法，分别对q[p:q-1]和a[q+1:r]进行排序
|
||
3. 合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行，所以在a[p:q-1]和a[q+1:r]完成排序后无需额外计算，a[p:r]的排序就已经完成
|
||
|
||
JAVA实现
|
||
|
||
```java
|
||
public class qSort
|
||
{
|
||
private static void qSort(int p,int r)
|
||
{
|
||
if(p<r)
|
||
{
|
||
int q = partition(p,r);
|
||
qSort(p,q-1);
|
||
qSort(q+1,r);
|
||
|
||
}
|
||
}
|
||
|
||
private static int partition(int p,int r)
|
||
{
|
||
int i = p,
|
||
j=r+1;
|
||
Comparable x = a[p];
|
||
//将<x的元素交换到左边区域
|
||
//将>x的元素交换到右边区域
|
||
while(true)
|
||
{
|
||
while(a[++i].compareTo(x)<0&&i<r);
|
||
while(a[--j].compareTo(x)>0);
|
||
if(i>=j)
|
||
break;
|
||
MyMath.swap(a,i,j);
|
||
}
|
||
a[p]=a[j];
|
||
a[j]=x;
|
||
return j;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
C++实现
|
||
|
||
```c++
|
||
Paritition1(int A[],int low,int high)
|
||
{
|
||
int pivot = A[low];
|
||
while (low < high)
|
||
{
|
||
while(low < high && A[high] >= pivot)
|
||
{
|
||
--high;
|
||
}
|
||
A[low] = A[high];
|
||
|
||
}
|
||
while (low < high && A[low] <= pivot)
|
||
{
|
||
++low;
|
||
}
|
||
A[low] = pivot;
|
||
return low;
|
||
}
|
||
|
||
void QuickSort(int A[],int low,int high)
|
||
{
|
||
if(low<high)
|
||
{
|
||
int pivot = Paritition1(A,low,high);
|
||
QuickSort(A,low,pivot - 1);
|
||
QuickSort(A,pivot + 1，high);
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
-------------------
|
||
|
||
#### 冒泡排序
|
||
|
||
主要思想：
|
||
1. 对一对相邻的元素比较，前者大于后者则交换它们
|
||
2. 对数组中所有元素都做此操作，直到最后，最大的数会向泡泡一样冒到数组末尾
|
||
3. 重复操作，每次都跳过上一次的最后一个元素,直到没有元素需要比较
|
||
|
||
|
||
JAVA
|
||
```java
|
||
public class BubbleSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
//复制到目标数组
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
}
|
||
for(int i = 1; i < arr.length; i++)
|
||
{
|
||
boolean flag =true;
|
||
|
||
for(int j = 0;j < arr.length - i;j++)
|
||
{
|
||
if(arr[j] > arr[j+1])
|
||
{
|
||
int tmp = arr[j];
|
||
arr[j] = arr[j+1];
|
||
arr[j+1] = tmp;
|
||
|
||
flag = false;
|
||
}
|
||
}
|
||
if(flag)
|
||
{
|
||
break;
|
||
}
|
||
return arr;
|
||
}
|
||
|
||
|
||
}
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
void BubbleSort(int arr[],int n)
|
||
{
|
||
for(int i = 0 ; i < n - 1;i++)
|
||
{
|
||
for(int j = 0;j < n-i-1;j++)//比较大小
|
||
{
|
||
if(arr[j]>arr[j+1])
|
||
}
|
||
int temp = arr[j];//交换位置
|
||
arr[j] = arr[j+1];
|
||
arr[j+1]=temp;
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
-------------
|
||
|
||
#### 选择排序
|
||
|
||
主要思想
|
||
1. 在没排序的序列中找到最小的元素，存放到开始位置
|
||
2. 在剩余元素中找到最小元素，存放到前一个元素的下一个位置
|
||
3. 重复步骤直到完成
|
||
|
||
JAVA
|
||
|
||
```java
|
||
public class SelectionSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
//复制到目标数组
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
|
||
|
||
//计算比较次数
|
||
for(int i = 0;i < arr.length - 1;i++)
|
||
{
|
||
int min = i;
|
||
|
||
for (int j = i + 1;j < arr.length;j++)
|
||
{
|
||
if(arr[j] < arr[min])
|
||
{
|
||
//记录当前找到的最小元素的下标
|
||
min = j;
|
||
}
|
||
|
||
}
|
||
//将找到的最小值和i位置所在的值进行交换
|
||
if(i ! = min)
|
||
{
|
||
int tmp = arr[i];
|
||
arr[i] = arr[min];
|
||
arr[min] = tmp;
|
||
}
|
||
}
|
||
return arr;
|
||
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
void selectSort(vector<int>& nums,int n)
|
||
{
|
||
for(int i = 0; i < n;i++)
|
||
{
|
||
int min = i;
|
||
|
||
|
||
for(int j = i+1;i < n;j++)//遍历取得最小值
|
||
{
|
||
if(nums[j] < nums[min])
|
||
{
|
||
min = j;
|
||
}
|
||
}
|
||
if(min != i) //移动到末尾
|
||
{
|
||
int tmp = nums[i];
|
||
nums[i] = nums[min];
|
||
nums[min] = tmp;
|
||
}
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
--------------------------------------
|
||
|
||
#### 插入排序
|
||
|
||
1. 将第一个元素视为已排列的有序数组，之后的元素视为未排列的无序数组
|
||
2. 从头到尾依次遍历未排序序列，将遍历到的元素插入到有序数组的适当位置
|
||
|
||
JAVA
|
||
|
||
```java
|
||
public class InsertionSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
//复制到目标数组
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
|
||
//从下标为1的元素开始遍历，寻找合适位置插入
|
||
for(int i = 1; i < arr.length;i++)
|
||
{
|
||
//缓存要插入的值
|
||
int tmp = arr[i];
|
||
|
||
//依次与有序数列中的数比较，找到合适位置
|
||
int j = i;
|
||
while(j>0 && tmp<arr[j-1])
|
||
{
|
||
arr[j] = arr[j-1];
|
||
j--;
|
||
}
|
||
//插入
|
||
if(j != i)
|
||
{
|
||
arr[j] = tmp
|
||
}
|
||
}
|
||
return arr;
|
||
|
||
}
|
||
|
||
}
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
void InsertionSort(int A[],int n)
|
||
{
|
||
for(int i=1;i<n;i++)
|
||
{
|
||
int get = A[i]; //缓存要排序的数
|
||
int j = i - 1;
|
||
while (j>=0 && A[j]>get)//与已排序的有序数组比较
|
||
{
|
||
A[j+1]=A[j];//如果该数更大则右移
|
||
j--;
|
||
}
|
||
A[j+1] = get;
|
||
}
|
||
|
||
|
||
}
|
||
|
||
```
|
||
|
||
------------------------------------------
|
||
|
||
#### 希尔排序
|
||
|
||
1. 将整个待排列数组分为增量序列$t_1,t_2,\cdots,t_k且t_i>t_j,t_k=1$
|
||
2. 按照增量序列的个数K，对序列进行k趟排序
|
||
3. 每次排序时根据$t_i$的值将未排序序列分割为若干个长度为m的子序列，分别进行插入排序。当i为1时，整个序列视为一个表
|
||
|
||
JAVA
|
||
|
||
```java
|
||
public class ShellSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
//复制到目标数组
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
|
||
|
||
int gap =1;
|
||
while(gap < arr.length/3)
|
||
{
|
||
gap = gap * 3 + 1;
|
||
|
||
}
|
||
|
||
while(gap > 0)
|
||
{
|
||
for(int i =gap; i<arr.length;i++)
|
||
{
|
||
int tmp = arr[i];
|
||
int j = i-gap;
|
||
while(j >= 0 && arr[j]>tmp)
|
||
{
|
||
arr[j+gap]=arr[j];
|
||
j-=gap;
|
||
}
|
||
arr[j+gap] = tmp;
|
||
}
|
||
gap = (int) Math.floor(gap/3);
|
||
}
|
||
return arr;
|
||
|
||
}
|
||
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
const int INCRGAP = 3;
|
||
void shellSort(int a[],int len)
|
||
{
|
||
int insertNum = 0;
|
||
unsigned gap = len/INCRGAP + 1;//初始化步长，应该确保步长为1
|
||
while(gap)
|
||
{
|
||
for(unsigned i = gap;i<len;++i)//分组子序列
|
||
{
|
||
insertNum = a[i];//缓存当前元素值
|
||
unsigned j = i;
|
||
while(j>=gap && insertNum< a[j-gap])//寻找插入位置
|
||
{
|
||
a[j] = a[j-gap];
|
||
j -= gap;
|
||
}
|
||
a[j] = insertNum;
|
||
}
|
||
gap = gap/INCRGAP;
|
||
}
|
||
}
|
||
```
|
||
|
||
-----------------------------------
|
||
|
||
#### 堆排序
|
||
|
||
1. 将要排序的数组构造为堆，根据升序或降序选择大顶堆或小顶堆
|
||
2. 互换堆首和堆尾
|
||
3. 将堆的尺寸缩小1，将新的数组顶点位置调整到对应位置
|
||
4. 重复步骤2，直到堆的尺寸为1
|
||
|
||
JAVA
|
||
|
||
```java
|
||
public class HeapSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
|
||
int len = arr.length;
|
||
|
||
buildMaxHeap(arr,len);
|
||
|
||
for(int i = len - i; i > 0;i--)
|
||
{
|
||
swap(arr,0,i);
|
||
len--;
|
||
heapify(arr,0,len);
|
||
}
|
||
return arr;
|
||
}
|
||
|
||
private void buildMaxHeap(int[],int len)
|
||
{
|
||
for(int i =(int) Math.floor(len/2);i>= 0;i--)
|
||
{
|
||
heapify(arr,i,len);
|
||
}
|
||
}
|
||
|
||
private void heapify(int[] arr,int i,int len)
|
||
{
|
||
int left =2 * i + 1;
|
||
int right = 2 * i + 2;
|
||
int largest = i;
|
||
|
||
if(left < len && arr[left]>arr[largest])
|
||
{
|
||
largest = left;
|
||
}
|
||
|
||
if(right < len && arr[right]> arr[largest])
|
||
{
|
||
largest = right;
|
||
}
|
||
|
||
if(largest !=i)
|
||
{
|
||
swap(arr,i,largest);
|
||
heapify(arr,largest,len);
|
||
}
|
||
}
|
||
private void swap(int[] arr,int i,int j)
|
||
{
|
||
int temp = arr[i];
|
||
arr[i] = arr[j];
|
||
arr[j] = temp;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
void buildMaxHeap(int A[],int n)
|
||
{
|
||
for(int i =n/2-1;i >= 0;i--)
|
||
{
|
||
maxHeapIfy(A,i,n);
|
||
}
|
||
}
|
||
|
||
void maxHeapIfy(int A[],int i,int n)
|
||
{
|
||
int l = 2 * i + 1;
|
||
|
||
int r = 2 * i + 1;
|
||
|
||
int largest = i;
|
||
|
||
if(l<n && A[l]>A[largest])
|
||
{
|
||
largest = l ;
|
||
}
|
||
if(l<n && A[r]>A[largest])
|
||
{
|
||
largest = r ;
|
||
}
|
||
if(largest != i)
|
||
{
|
||
swap(A[i],A[largest]);
|
||
maxHeapIfy(A,largest,n);
|
||
}
|
||
}
|
||
|
||
void heapSort(int A[],int n)
|
||
{
|
||
buildMaxHeap(A,n);
|
||
for(int i = n-1;i> 0 ;i--)
|
||
{
|
||
swap(A[0],A[i]);
|
||
maxHeapIfy(A,0,i);
|
||
}
|
||
}
|
||
|
||
|
||
```
|
||
|
||
|
||
|
||
-------------------------------------
|
||
|
||
|
||
|
||
#### 计数排序
|
||
|
||
1. 找出待排序的数组中国最大和最小的元素，从而确定缓存数组的最大长度
|
||
2. 根据每个值为i的元素出现的次数，存入缓存数组的第i项
|
||
3. 累加所有计数
|
||
4. 反向填充目标数组
|
||
|
||
|
||
JAVA
|
||
|
||
```java
|
||
public class HeapSort
|
||
{
|
||
public int[] sort(int[] sourceArray)
|
||
{
|
||
int[] arr = Arrays.copyof(sourceArray,sourceArray.length);
|
||
|
||
int maxValue = getMaxValue(arr);
|
||
|
||
return countingSort(arr,maxValue);
|
||
|
||
}
|
||
|
||
private int[] countingSort(int[] arr,int maxValue)
|
||
{
|
||
int bucketLen = maxValue + 1;
|
||
int[] bucket = new int[bucketLen];
|
||
|
||
for(int value :arr)
|
||
{
|
||
bucket[value]++;
|
||
}
|
||
|
||
int sortedIndex = 0;
|
||
for(int j = 0; j < bucketLen;j++)
|
||
{
|
||
while(bucket[j]>0)
|
||
{
|
||
arr[sortedIndex++] = j;
|
||
bucket[j]--;
|
||
}
|
||
}
|
||
return arr;
|
||
}
|
||
|
||
private int getMaxValue(int[] arr)
|
||
{
|
||
int maxValue = arr[0];
|
||
for(int value : arr)
|
||
{
|
||
if(maxValue < value)
|
||
{
|
||
maxValue = value;
|
||
}
|
||
}
|
||
return maxValue;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
#include <iostream>
|
||
#include <algorithm>
|
||
#include <vector>
|
||
#include <string>
|
||
#include <cstdlib>
|
||
using namespace std;
|
||
|
||
vector<int> CountSort(const vector<int>& vec)
|
||
{
|
||
int length = vec.size();
|
||
if(length <= 1)
|
||
{
|
||
return vec;
|
||
}
|
||
else
|
||
{
|
||
int max = *max_element(vec.begin(),vec.end());
|
||
int min = *min_element(vec.begin(),vec.end());
|
||
|
||
vector<int> countArray(max - min + 1,0);
|
||
|
||
for(int i = 0;i < length;i++)
|
||
{
|
||
++countArray[vec[i] - min];
|
||
}
|
||
|
||
vector<int> sortArray;
|
||
for(int i = 0;i < countArray.size();++i)
|
||
{
|
||
for(int j = 0;j < countArray[i];++j)
|
||
{
|
||
sortArray.push_back(min + i);
|
||
}
|
||
}
|
||
return sortArray;
|
||
}
|
||
}
|
||
|
||
|
||
```
|
||
|
||
|
||
-----------------------------
|
||
|
||
|
||
#### 桶排序
|
||
|
||
1. 利用函数映射关系将待排序数组的元素分配到桶中
|
||
2. 将元素在桶中排序
|
||
|
||
|
||
```java
|
||
public class BuckSort
|
||
{
|
||
private static final InserSort insertSort = new InsertSort();
|
||
|
||
public int[] sort(int[] sourceArray) throws Exception
|
||
{
|
||
int[] arr = Arrays.copy0f(sourceArray,sourceArray.length);
|
||
|
||
return bucketSort(Arr,5);
|
||
}
|
||
|
||
private int[] bucketSort(int[] arr,int bucketSize) throws Exception
|
||
{
|
||
if(arr.length == 0)
|
||
{
|
||
return arr;
|
||
}
|
||
|
||
int minValue = arr[0];
|
||
int maxValue = arr[0];
|
||
for(int value : arr)
|
||
{
|
||
if(value < minValue)
|
||
{
|
||
minValue = value;
|
||
|
||
}
|
||
else if(value > maxValue)
|
||
{
|
||
maxValue = value;
|
||
}
|
||
}
|
||
|
||
int bucketCount = (int) Math.floor((maxValue - minValue)/bucketSize) + 1;
|
||
|
||
int[][] buckets = new int[bucketCount][0];
|
||
|
||
for(int i = 0;i < arr.length;i++)
|
||
{
|
||
int index = (int)Math.floor((arr[i]-minValue)/bucketSize);
|
||
buckets[index] = arrAppend(buckets[index],arr[i]);
|
||
}
|
||
|
||
int arrIndex = 0;
|
||
for(int[] bucket : buckets)
|
||
{
|
||
if(buckets.length <= 0)
|
||
{
|
||
continue;
|
||
}
|
||
|
||
bucket = insertSort.sort(bucket);
|
||
for(int value : bucket)
|
||
{
|
||
arr[arrIndex++] = value;
|
||
}
|
||
}
|
||
return arr;
|
||
}
|
||
/*自动扩容桶的数量*/
|
||
private int[] arrAppend(int[] arr,int value)
|
||
{
|
||
arr = Arrays.copy0f(arr,arr.length+1);
|
||
arr[arr.length - 1] = value;
|
||
return arr;
|
||
}
|
||
|
||
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
```c++
|
||
#include <iterator>
|
||
#include <iostream>
|
||
#include <vector>
|
||
using namespace std;
|
||
const int BUCKET_NUM = 10;
|
||
|
||
struct ListNode
|
||
{
|
||
explicit ListNode(int i = 0):mData(i),mNext(NULL)
|
||
{
|
||
ListNode* mNext;
|
||
int mData;
|
||
}
|
||
};
|
||
|
||
ListNode* insert(ListNode* head,int val)
|
||
{
|
||
ListNode dummyNode;
|
||
ListNode *newNode = new ListNode(val);
|
||
ListNode *pre,*curr;
|
||
dummyNode.mNext = head;
|
||
pre = &dummyNode;
|
||
curr = head;
|
||
while(NULL!=curr && curr->mData<=val)
|
||
{
|
||
pre = curr;
|
||
curr = curr->mNext;
|
||
}
|
||
newNode->mNext = curr;
|
||
pre->mNext = newNode;
|
||
return dummyNode.mNext;
|
||
}
|
||
|
||
ListNode* Merge(ListNode *head1,ListNode *head2)
|
||
{
|
||
ListNode dummyNode;
|
||
ListNode *dummy = &dummyNode;
|
||
while(NULL!=head1 && NULL!= head2)
|
||
{
|
||
if(head1->mData <= head2->mData)
|
||
{
|
||
dummy->mNext = head1;
|
||
head1 = head1->mNext;
|
||
}
|
||
else
|
||
{
|
||
dummy->mNext = head2;
|
||
head2 = head2 ->mNext;
|
||
}
|
||
dummy = dummy ->mNext;
|
||
}
|
||
if(NULL!=head1) dummy->mNext = head1;
|
||
if(NULL!=head2) dummy->mNext = head2;
|
||
|
||
return dummyNode.mNext;
|
||
}
|
||
|
||
void BuckSort(int n,int arr[])
|
||
{
|
||
vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
|
||
for(int i=0;i<n;++i)
|
||
{
|
||
int index = arr[i]/BUCKET_NUM;
|
||
ListNode *head = buckets.at(index);
|
||
buckets.at(index)=insert(head,arr[i]);
|
||
}
|
||
|
||
ListNode *head = buckets.at(0);
|
||
for(int i=1;i<BUCKET_NUM;++i)
|
||
{
|
||
head = Merge(head,buckets.at(i));
|
||
}
|
||
for(int i=0;i<n;++i)
|
||
{
|
||
arr[i] = head->mData;
|
||
head = head->mNext;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
|
||
-----------------------------
|
||
|
||
#### 基数排序
|
||
|
||
将整数按位数分割为不同数字，按各位数比较大小
|
||
|
||
在桶的分配方式上根据键值的每位数字来分配桶
|
||
|
||
|
||
```java
|
||
public class RadixSort
|
||
{
|
||
public int[] sort(int[] sourceArray) throws Exception
|
||
{
|
||
int[] arr = Arrays.copy0f(sourceArray,sourceArray.length);
|
||
|
||
int maxDigit = getMaxDigit(arr);
|
||
return radixSort(arr,maxDigit);
|
||
}
|
||
|
||
/*
|
||
获取最高位数
|
||
*/
|
||
|
||
private int getMaxDigit(int[] arr)
|
||
{
|
||
int maxValue = getMaxValue(arr);
|
||
return getNumLenght(maxValue);
|
||
}
|
||
|
||
private int getMaxValue(int[] arr)
|
||
{
|
||
int maxValue = arr[0];
|
||
for(int value : arr)
|
||
{
|
||
if(maxValue < value)
|
||
{
|
||
maxValue = value;
|
||
}
|
||
}
|
||
return maxValue;
|
||
}
|
||
|
||
|
||
private int getNumLenght(long num)
|
||
{
|
||
if(num == 0)
|
||
{
|
||
return 1;
|
||
}
|
||
int length = 0;
|
||
for(long temp = num;temp !=0;temp/=10)
|
||
{
|
||
lenght++;
|
||
}
|
||
return lenght;
|
||
|
||
}
|
||
|
||
private int[] radixSort(int[] arr,int maxDigit)
|
||
{
|
||
int mod =10;
|
||
int dev =1;
|
||
|
||
for(int i = 0;i < maxDigit;i++,dev*=10,mod *= 10)
|
||
{
|
||
int[][] counter = new int[mod * 2][0];
|
||
|
||
for(int j= 0;j<arr.length;j++)
|
||
{
|
||
int bucket = ((arr[j]%mod)/dev)+mod;
|
||
counter[bucket] = arrAppend(counter[bucket],arr[j]);
|
||
}
|
||
|
||
int pos = 0;
|
||
for(int[] bucke:counter)
|
||
{
|
||
for(int value :bucket)
|
||
{
|
||
arr[pos++] = value;
|
||
}
|
||
}
|
||
}
|
||
return arr;
|
||
}
|
||
|
||
//自动扩容
|
||
|
||
private int[] arrAppend(int[] arr,int value)
|
||
{
|
||
arr = Arrays.copy0f(arr.length + 1);
|
||
arr[arr.length - 1] = value;
|
||
return arr;
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
C++
|
||
|
||
|
||
```c++
|
||
int maxbit(int data[],int n)
|
||
{
|
||
int maxData = data[0];
|
||
|
||
for(int i = 1;i< n;++i)
|
||
{
|
||
if(maxData < data[i])
|
||
{
|
||
maxData = data[i];
|
||
}
|
||
}
|
||
int d = 1;
|
||
int p = 10;
|
||
while (maxDate >= p )
|
||
{
|
||
maxData /= 10;
|
||
++d;
|
||
}
|
||
return d;
|
||
|
||
}
|
||
|
||
void radixSort(int data[],int n)
|
||
{
|
||
int d = maxbit(data,n);
|
||
int *tmp = new int[n];
|
||
int *count = new int[n];
|
||
int i,j,k;
|
||
int radix = 1;
|
||
for(i = 1;i <= d;i++)
|
||
{
|
||
for(j = 0;j < 10;j++)
|
||
{
|
||
count[j] = 0;
|
||
}
|
||
for(j = 0;j < n;j++)
|
||
{
|
||
k = (data[j]/radix) % 10;
|
||
count[k]++;
|
||
}
|
||
for(j = 1;j < 10;j++)
|
||
{
|
||
count[j] = count[j-1]+count[j];
|
||
|
||
}
|
||
for(j = n-1;j>= 0 ;j--)
|
||
{
|
||
k = (data[j]/radix) % 10;
|
||
tmp[count[k] - 1] = data[j];
|
||
count[k]--;
|
||
}
|
||
for(j = 0;j < n;j++)
|
||
{
|
||
data[j] = tmp[j];
|
||
|
||
}
|
||
radix = radix * 10;
|
||
}
|
||
delete []tmp;
|
||
delete []count;
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
-----------------------------
|