InkSoul/content/algorithm/排序合集.md

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

```



-----------------------------