排序种类.PNG
排序时间复杂度总结.PNG
以下是个人总结的各类排序代码：
一：非线性排序（适合大n排序）：
1.交换-冒泡：
public static void bubbleSort(int arr[]){
int size = arr.length;
for(int i=0;i<size;i++){
for(int j=size-1;j>i;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
1.交换-冒泡优化版（在之后的排序中，都尽量减少swap调用，用空间换时间。另外，冒泡还可以设置flag布尔值优化，当前一次冒泡过程中没有交换时flag设置true，可以提前停止整个排序）：
public static void bubbleSort(int arr[]){
for(int i=0;i<size;i++){
int temp = arr[size-1];
for(int j=size-1;j>i;j--){
if(arr[j-1]>temp){
arr[j] = arr[j-1];
}else{
arr[j] = temp;
temp = arr[j-1];
}
}
}
}
2.交换-快速排序（temp变量导致了空间复杂度提升至o(logn)，用空间换时间）：
public static void quickSort(int arr[],int left ,int right){
int temp=arr[left];
int i=left;
int j=right;
if(j>i){
while(j>i){
while(j>i && arr[j]>=temp){
j--;
}
while(j>i && arr[i]<=temp){
i++;
}
if(j>i){
swap(arr,i,j);
/* int t=arr[i];
arr[i]=arr[j];
arr[j]=t;*/
}
}
if(i>left){//i==j
swap(arr,left,i);
}
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}
}
3.插入-简单插入排序（这里是优化版，用空间换时间，标准版参见希尔排序）：
//插入排序就是扑克牌排序
public static void insertSort(int []arr){
for(int i=1;i<arr.length;i++){
int j = i;
int temp = arr[j];
while(j-1>=0 && arr[j-1]>temp){
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
}
4.插入-希尔排序：
//希尔排序就是插入排序的细粒度版
public static void hillSort(int []arr){
// i -> gap
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++){
int j = i;
while(j-gap >= 0 && arr[j-gap] > arr[j]){
swap(arr,j,j-gap);
j-=gap;
//这里也可以用上面 插入排序 的代码，减少swap的调用
}
}
}
}
5.选择-简单选择排序：
public static void selectionSort(int arr[]){
for(int j=1;j<arr.length;j++){
int max=j-1;
int maxV=arr[j-1];
for(int i=j;i<arr.length;i++){
if(arr[i]>maxV){
max=i;
maxV=arr[i];
}
}
if(max!=j-1){
swap(arr,j-1,max);
}
}
}
6.选择-堆排序(非递归版本)：
public static void dumpSort(int arr[]){
for(int i=(arr.length>>2-1);i>=0;i--){
adjustHeap(arr,i,arr.length);
}//
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
public static void adjustHeap(int arr[],int pNode,int heapSize){
//递归性能比较差，这里是迭代版，不过可读性差点
int temp=arr[pNode];
for(int cNode = pNode*2+1;cNode < heapSize;cNode = cNode*2+1){
if(cNode+1 < heapSize && arr[cNode+1] > arr[cNode]){
cNode++;
}
if(arr[cNode]>temp){
arr[pNode] = arr[cNode];
pNode = cNode;
}else{
break;
}
}
arr[pNode]=temp;
}
7.归并-二路归并排序（temp[]数组导致了空间复杂度提升至o(n)，用空间换时间）：
public static void mergeSort(int arr[],int left, int right,int temp[]){
if(left<right){
int mid=(right+left)/2;
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int arr[],int left ,int mid,int right,int temp[]){
int i=left ;
int j=mid+1;
int k=0;
while(i<=mid&&j<=right){
if(arr[i]<=arr[j]){
temp[k++]=arr[i++];
}
else{
temp[k++]=arr[j++];
}
}
while(i<=mid){
temp[k++]=arr[i++];
}
while(j<=right){
temp[k++]=arr[j++];
}
k=0;
while(left<=right){
arr[left++]=temp[k++];
}
}
8.归并-多路归并排序：原理是类似的，这里就不贴代码了。
二：非线性排序（适合小n排序）：
1.桶排序:
bucket这个名字我想到了hashmap里的那个bucket，实现有点类似呢，不过这里不需要hash值，而是通过算区间跨度 = （最大值-最小值）/ （桶的数量（自定义n） - 1）分配成n个有区间的桶子，然后，遍历原始数列，把元素对号入座放入各个桶中：
public static double[] bucketSort(double[] array){
//1.得到数列的最大值和最小值，并算出差值d
double max = array[0];
double min = array[0];
for(int i=1; i<array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
double d = max - min;
//2.初始化桶
int bucketNum = array.length;
ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketList.add(new LinkedList<Double>());
}
//3.遍历原始数组，将每个元素放入桶中
for(int i = 0; i < array.length; i++){
int num = (int)((array[i] - min) * (bucketNum-1) / d);
bucketList.get(num).add(array[i]);
}
//4.对每个通内部进行排序
for(int i = 0; i < bucketList.size(); i++){
//JDK底层采用了归并排序或归并的优化版本
Collections.sort(bucketList.get(i));
}
//5.输出全部元素
double[] sortedArray = new double[array.length];
int index = 0;
for(LinkedList<Double> list : bucketList){
for(double element : list){
sortedArray[index] = element;
index++;
}
}
return sortedArray;
}
2.计数排序-不稳定版（适合一定量的连续正整数区间，单纯的记录某个数出现的次数）:
public static int[] countSort(int[] array) {
//1.得到数列的最大值
int max = array[0];
for(int i=1; i<array.length; i++){
if(array[i] > max){
max = array[i];
}
}
//2.根据数列最大值确定统计数组的长度，这里其实可以做优化，数组长度取最大值-最小值+1就行了。
int[] countArray = new int[max+1];
//3.遍历数列，填充统计数组
for(int i=0; i<array.length; i++){
countArray[array[i]]++;
}
//4.遍历统计数组，输出结果
int index = 0;
int[] sortedArray = new int[array.length];
for(int i=0; i<countArray.length; i++){
//某个数出现几次就最终输出几次
for(int j=0; j<countArray[i]; j++){
sortedArray[index++] = i;
}
}
return sortedArray;
}
2.计数排序-稳定版（统计数组值修改为当前最大排名）：
public static int[] countSort2(int[] array) {
//1.得到数列的最大值和最小值，并算出差值d
int max = array[0];
int min = array[0];
for(int i=1; i<array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
int d = max - min;
//2.创建统计数组并统计对应元素个数
int[] countArray = new int[d+1];
for(int i=0; i<array.length; i++) {
countArray[array[i]-min]++;
}
//3.统计数组做变形，后面的元素等于前面的元素之和
int sum = 0;
for(int i=0;i<countArray.length;i++) {
sum += countArray[i];
countArray[i] = sum;
}
//4.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
int[] sortedArray = new int[array.length];
for(int i=array.length-1;i>=0;i--) {
sortedArray[countArray[array[i]-min]-1]=array[i];
countArray[array[i]-min]--;
}
return sortedArray;
}
3.基数排序（先按个位数排序，再按十位...一直到最大数的最大位）：
private static void radixSort(int[] array,int d)
{
int n=1;//代表位数对应的数：1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d)
{
for(int num:array) //将数组array里的每个数字放在相应的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
{
if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0，用于下一次位排序
}
n*=10;
k=0;//将k置0，用于下一轮保存位排序结果
}
}
