---

1. 插入排序

步骤：

1.从第一个元素开始，该元素可以认为已经被排序
2.取下一个元素tem，从已排序的元素序列从后往前扫描
3.如果该元素大于tem，则将该元素移到下一位
4.重复步骤3，直到找到已排序元素中小于等于tem的元素
5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
6.重复步骤2~5

动图演示如下：
思路：
  在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
  但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

代码如下：

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		//记录有序序列最后一个元素的下标
		int end = i;
		//待插入的元素
		int tem = arr[end + 1];
		//单趟排
		while (end >= 0)
		{
			//比插入的数大就向后移
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			//比插入的数小，跳出循环
			else
			{
				break;
			}
		}
		//tem放到比插入的数小的数的后面
		arr[end  + 1] = tem;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
	}
}

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)

2.希尔排序

步骤：
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
动图如下：

思路：
希尔排序，先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序，此时插入排序的时间复杂度为O(N)，

代码如下：

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap>1)
	{
		//每次对gap折半操作
		gap = gap / 2;
		//单趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

时间复杂度平均：O(N^1.3)
空间复杂度：O(1)

3.选择排序

思路：
每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

动图如下：

代码如下：

//选择排序
void swap(int* a, int* b)
{
	int tem = *a;
	*a = *b;
	*b = tem;
}
void SelectSort(int* arr, int n)
{
	//保存参与单趟排序的第一个数和最后一个数的下标
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//保存最大值的下标
		int maxi = begin;
		//保存最小值的下标
		int mini = begin;
		//找出最大值和最小值的下标
		for (int i = begin; i <= end; ++i)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//最小值放在序列开头
		swap(&arr[mini], &arr[begin]);
		//防止最大的数在begin位置被换走
		if (begin == maxi)
		{
			maxi = mini;
		}
		//最大值放在序列结尾
		swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1)

4.冒泡排序

思路：
左边大于右边交换一趟排下来最大的在右边

动图如下：

代码如下：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int end = n;
	while (end)
	{
		int flag = 0;
		for (int i = 1; i < end; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1)

5.堆排序

堆排可看之间这篇博文----->[堆排]

6.快速排序

5.1 hoare版本(左右指针法)

思路：
1、选出一个key，一般是最左边或是最右边的。
2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4.此时key的左边都是小于key的数，key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

单趟动图如下：

代码如下：

//快速排序   hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{
	//只有一个数或区间不存在
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	//选左边为key
	int keyi = begin;
	while (begin < end)
	{
		//右边选小   等号防止和key值相等    防止顺序begin和end越界
		while (arr[end] >= arr[keyi] && begin < end)
		{
			--end;
		}
		//左边选大
		while (arr[begin] <= arr[keyi] && begin < end)
		{
			++begin;
		}
		//小的换到右边，大的换到左边
		swap(&arr[begin], &arr[end]);
	}
	swap(&arr[keyi], &arr[end]);
	keyi = end;
	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr,keyi + 1,right);
}

时间复杂度:

快速排序的过程类似于二叉树其高度为logN，每层约有N个数，如下图所示：

5.2 挖坑法

5.2.1 递归

思路：
挖坑法思路与hoare版本(左右指针法)思路类似
1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）

后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

单趟动图如下：

代码如下：

//快速排序法  挖坑法
void QuickSort1(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin,right = end;
	int key = arr[begin];
	while (begin < end)
	{
		//找小
		while (arr[end] >= key && begin < end)
		{
			--end;
		}
		//小的放到左边的坑里
		arr[begin] = arr[end];
		//找大
		while (arr[begin] <= key && begin < end)
		{
			++begin;
		}
		//大的放到右边的坑里
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	int keyi = begin;
	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

5.2.2 非递归

//单趟排
int PartSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	while (begin < end)
	{
		while (key <= arr[end] && begin < end)
		{
			--end;
		}
		arr[begin] = arr[end];
		while (key >= arr[begin] && begin < end)
		{
			++begin;
		}
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	int meeti = begin;
	return meeti;
}

void QuickSortNoR(int* arr, int begin, int end)
{
	stack<int> st;
	//先入右边
	st.push(end);
	//再入左边
	st.push(begin);
	while (!st.empty())
	{
		//左区间
		int left = st.top();
		st.pop();
		//右区间
		int right = st.top();
		st.pop();
		//中间数
		int mid = PartSort(arr, left, right);
		//当左区间>=mid-1则证明左区间已经排好序了
		if (left < mid - 1)
		{
			st.push(mid - 1);
			st.push(left);
		}
		//当mid+1>=右区间则证明右区间已经排好序
		if (right > mid + 1)
		{
			st.push(right);
			st.push(mid + 1);
		}
	}
}

5.3 前后指针法

思路：
1、选出一个key，一般是最左边或是最右边的。
2、起始时，prev指针指向序列开头，cur指针指向prev+1。
3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作

//快速排序法  前后指针版本
void QuickSort2(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int cur = begin, prev = begin - 1;
	int keyi = end;
	while (cur != keyi)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	swap(&arr[++prev],&arr[keyi]);
	keyi = prev;
	//[begin,keyi -1]keyi[keyi+1,end]
	QuickSort2(arr, begin, keyi - 1);
	QuickSort2(arr, keyi + 1, end);

}

写在前面的话

       虽然已经有很多人总结过这十大排序算法，优秀的文章也不少，但是Java完整版的好像不多，还存在某些文章代码存在错误的情况，同时也为了自己练手，决定把所有的写一遍巩固下，同时也真诚的希望阅读到这篇文章的小伙伴们可以自己去从头敲一遍，不要粘贴复制！希望我的文章对你有所帮助，每天进步一点点！！！

       我用通俗的理解写下对算法的解释，对某个算法的运行过程不是很理解的话或者想看比较官方的解释的话，单独搜索某个算法，看几篇不同的解释，就可以有自己的理解了，这里我主要展示代码以及进行通俗的解释！整起来，再强调一次，一定要自己敲一遍，这样才能理解的更深刻！

十大排序算法对比

关于最后一列的稳定性，我稍微解释下，例如对序列：1 2 4 2 6 排序，序列中存在两个2，如果我们把这两个2标记上（让他俩不同），排序之后，前面的2还在前面，那么就称这种排序是稳定的，反之不稳定。

冒泡排序

简单解释：
       原理就如算法名字一样，就像水中的气泡一样，每次我都把最大的或最小的放到最后面，这样总共需要n-1趟即可完成排序，这就是第一层循环，第二次循环就是遍历未被固定的那些数（理解成数组左边的数，因为每层循环都会把最大或最小的数升到最右边固定起来，下次就不遍历这些数了），两层循环遍历结束后，所有的数就排好序了。
       两层循环所以冒泡排序算法的时间复杂度是O($n^2$)，是一个非常高的时间复杂度，我在下面的代码进行了优化，加了一个标志位，如果上一次循环未发生交换，就说明已经是有序的了，就不继续下去了，反之继续进行下一轮。

本文的图片来源网络，仅用于大家学习，侵权联系删除！（下同）

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: BubbleSort
 * @Description: 冒泡排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:31
 */
public class BubbleSort {

    //冒泡排序
    public static void bubbleSort(int[] arr, boolean ascending) { //exchange标志表示为升序排序还是降序排序

        boolean flag = true; //加一个标志位，记录上一次是否发生了交换，如果是，我们则进行下一轮，如果没有，说明已经冒泡好了

        for (int i = 1; i < arr.length && flag; i++) { //控制次数，第几趟排序，只需要n-1趟，有交换时进行，只有flag=false就说明上一次一个元素都没有进行交换

            /*System.out.print("第"+i+"次遍历：");
            for (int i1 : arr) {
                System.out.print(i1+" ");
            }
            System.out.println();*/

            flag = false; //假定未交换

            for (int j = 0; j < arr.length - i; j++) {

                if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //控制升序还是降序
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }

            }
        }
    }

    //冒泡排序 -- 默认不传参升序
    public static void bubbleSort(int[] arr) {
        bubbleSort(arr, true);
    }
}

测试代码：

升序排序（从小到大）

package com.keafmd.Sequence;

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * Keafmd
 *
 * @ClassName: Sort
 * @Description: 十大排序算法
 * @author: 牛哄哄的柯南
 * @date: 2021-06-16 21:27
 */
public class Sort {
    public static void main(String[] args) {

        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;

        //测试冒泡排序
        System.out.println("测试冒泡排序:");
        temparr = nums.clone();
        BubbleSort.bubbleSort(temparr);
        //逆序排序
        //BubbleSort.bubbleSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

    }
}

运行结果：

测试冒泡排序:
-66 -13 -1 1 4 9 12 25 25 26 34 47 58 99 162 10093 

降序排序（从大到小）

//测试冒泡排序
System.out.println("测试冒泡排序:");
temparr = nums.clone();
BubbleSort.bubbleSort(temparr,false);
for (int i = 0; i < temparr.length; i++) {
    System.out.print(temparr[i] + " ");
}
System.out.println();

运行结果：

测试冒泡排序:
10093 162 99 58 47 34 26 25 25 12 9 4 1 -1 -13 -66 

下面几个算法的测试也就是换了下类名和方法名（换成相应的排序算法），如果想降序就在数组后面传个false即可。我就不一一复制了，我在最下面给出含所有算法的测试类，需要的自取即可。

快速排序

简单解释：
快速排序就是每次找一个基点（第一个元素），然后两个哨兵，一个从最前面往后走，一个从最后面往前面走，如果后面那个哨兵找到了一个比基点大的数停下来，前面那个哨兵找到比基点大的数停下来，然后交换两个哨兵找到的数，如果找不到最后两个哨兵就会碰到一起就结束，最后交换基点和哨兵相遇的地方的元素，然后就将一个序列分为比基点小的一部分和比基点大的一部分，然后递归左半部分和右半部分，最后的结果就是有序的了。

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: QuickSort
 * @Description: 快速排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:32
 */
public class QuickSort {

    //快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr, true);
    }

    public static void quickSort(int[] arr, boolean ascending) {
        if (ascending) {
            quickSort(arr, 0, arr.length - 1, true);
        } else {
            quickSort(arr, 0, arr.length - 1, false);
        }
    }

    public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
        if (ascending)
            quickSort(arr, begin, end);
        else
            quickSortDescending(arr, begin, end);
    }

    //快排序升序 -- 默认
    public static void quickSort(int[] arr, int begin, int end) {
        if (begin > end) { //结束条件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { // 两个哨兵（i左边，j右边）没有相遇
            while (arr[j] >= base && i < j) { //哨兵j没找到比base小的
                j--;
            }
            while (arr[i] <= base && i < j) { //哨兵i没找到比base大的
                i++;
            }
            if (i < j) { //如果满足条件则交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[begin] = arr[i];
        arr[i] = base;
        quickSort(arr, begin, i - 1); //递归调用左半数组
        quickSort(arr, i + 1, end); //递归调用右半数组

    }

    //快排序降序
    public static void quickSortDescending(int[] arr, int begin, int end) {
        if (begin > end) { //结束条件
            return;
        }
        int base = arr[begin];
        int i = begin, j = end;
        while (i < j) { // 两个哨兵（i左边，j右边）没有相遇
            while (arr[j] <= base && i < j) { //哨兵j没找到比base大的
                j--;
            }
            while (arr[i] >= base && i < j) { //哨兵i没找到比base小的
                i++;
            }
            if (i < j) { //如果满足条件则交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[begin] = arr[i];
        arr[i] = base;
        quickSortDescending(arr, begin, i - 1); //递归调用左半数组
        quickSortDescending(arr, i + 1, end); //递归调用右半数组

    }

}

直接选择排序

简单解释：
数组分为已排序部分（前面）和待排序序列（后面）
第一次肯定所有的数都是待排序的
从待排序的序列中找到最大或最小的那个元素，放到前面的已排序部分，然后一直找，不断缩小待排序的范围，直到所有的数都是已排序的了

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: SelectSort
 * @Description: 选择排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:33
 */
public class SelectSort {

    //直接选择排序
    public static void selectSort(int[] arr, boolean ascending) {
        for (int i = 0; i < arr.length; i++) {
            int m = i; //最小值或最小值的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) {
                    m = j; //找到待排序的数中最小或最大的那个数，记录下标
                }

            }
            //交换位置
            int temp = arr[i];
            arr[i] = arr[m];
            arr[m] = temp;

        }
    }

    public static void selectSort(int[] arr) {
        selectSort(arr, true);
    }
}

堆排序

先理解下大顶堆和小顶堆，看图
大顶堆，双亲结点的值比每一个孩子结点的值都要大。根结点值最大
小顶堆，双亲结点的值比每一个孩子结点的值都要小。根结点值最小

简单解释：
构建好大顶堆或小顶堆结构，这样最上面的就是最大值或最小值，那么我们取出堆顶元素，然后重新构建结构，一直取，一直重新构建，那么最后达到排序的效果了。

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: HeapSort
 * @Description: 堆排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:34
 */
public class HeapSort {

    //堆排序
    public static void heapSort(int[] arr) {
        //对传入的数组进行建立堆，这里默认建立大顶堆，进行升序排列
        heapSort(arr, true);
    }

    public static void heapSort(int[] arr, boolean maxheap) {

        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            sift(arr, i, arr.length , maxheap);
        }

        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {

            //现在的数组第一个就是根结点，最小值所在，进行交换，把它放到最右边
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;

            //重新建立堆
            sift(arr, 0, j , maxheap); //重新对堆进行调整
        }
    }

    //建立堆的方法
    /**
     * 私有方法，只允许被堆排序调用
     *
     * @param arr     要排序数组
     * @param parent  当前的双亲节点
     * @param len     数组长度
     * @param maxheap 是否建立大顶堆
     */
    private static void sift(int[] arr, int parent, int len, boolean maxheap) {

        int value = arr[parent]; //先取出当前元素i

        for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //从parent结点的左子结点开始，也就是2*parent+1处开始

            if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子结点小于右子结点，child指向右子结点
                child++; //右孩子如果比左孩子大，我们就将现在的孩子换到右孩子
            }

            //判断是否符合大顶堆的特性， 如果右孩子大于双亲，自然左孩子也大于双亲，符合
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换)
            if (maxheap ? value < arr[child] : value > arr[child]) {
                arr[parent]=arr[child];
                parent = child;
            }
            else {//如果不是，说明已经符合我们的要求了。
                break;
            }
        }
        arr[parent] =value; //将value值放到最终的位置


    }

}

归并排序

简单解释：
该算法是采用分治法，把数组不断分割，直至成为单个元素，然后比较再合并（合并的过程就是两部分分别从头开始比较，取出最小或最大元素的放到新的区域内，继续取两部分中最大或最小的元素，直到这两部分合并完，最后所有的都合并完，最后形成完整的有序序列）

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: MergeSort
 * @Description: 归并排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:35
 */
public class MergeSort {

    //归并排序
    public static void mergeSort(int []arr ,boolean ascending){
        int[] temp = new int[arr.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        mergeSort(arr,0,arr.length-1,temp,ascending);
    }
    public static void mergeSort(int []arr){
        mergeSort(arr,true);
    }

    /**
     *
     * @param arr 传入的数组
     * @param left 当前子数组的起始下标
     * @param right 当前子数组的结束下标
     * @param temp 拷贝暂存数组
     */
    public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){
        if(left<right){ //这里是递归结束的条件，我们是对半分，那当left==right的时候肯定大家都是只有一个元素了。

            //对半分，比如总长度是10，left=0，right=9，mid=4确实是中间分了，0~4，5~9
            //当长度9，left=0，right=8，mid=4，0~4，5~8
            int mid = left + (right-left)/2; // 防止越界的写法
            //int mid = (left+right)/2;

            mergeSort(arr,left,mid,temp,ascending); //左边归并排序，使得左子序列有序
            mergeSort(arr,mid+1,right,temp,ascending); //右边归并排序，使得右子序列有序

            merge(arr,left,mid,right,temp,ascending); //将两个有序子数组合并操作
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){
        int i = left; //左序列起始下标
        int j = mid+1; //右序列起始下标
        int t = 0; //临时数组指针
        while(i<=mid&&j<=right){
            if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ //比较两个序列第一个元素谁小，谁小先拷贝谁到temp，然后对应子序列下标加1
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while(i<=mid){ //将左边剩余元素填充进temp中——左序列有一些数总是比右边的大的数
            temp[t++] = arr[i++];
        }

        while(j<=right){ //将右序列剩余元素填充进temp中——右序列有一些数总是比左边的大的数
            temp[t++] = arr[j++];
        }

        t = 0;

        //将temp中的元素全部拷贝到原数组中
        while(left<=right){
            arr[left++] = temp[t++];
        }

    }

}

插入排序

简单解释：
最简单的理解就是打地主时我们拿到牌后的整理过程，从第二个牌（假设我们拿起来这个牌开始比较）开始，（说下升序）从后往前比较如果比前面的那个牌小，就把牌往后移动，直到找到一个合适的位置（这个位置的前面的那个牌不比这个要放下的牌大）就把这个牌放到这个位置，慢慢的前面的部分变得有序，直至全部有序即可。

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: StraghtInsertSort
 * @Description: 插入排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:36
 */
public class StraghtInsertSort {
    //插入排序
    public static void straghtInsertSort(int[] arr) {
        straghtInsertSort(arr, true);//默认进行升序
    }

    public static void straghtInsertSort(int[] arr, boolean ascending) {

        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j=0; //这就是那个合适的位置
            for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
                arr[j + 1] = arr[j];
            }
            //把牌放下，为啥是j+1，
            //是因为上面的循环遍历到不符合情况的时候 j是合适的位置的前面的那个数的位置
            //有点拗口，但是就是这个意思，看图方便理解下
            arr[j + 1] = temp;


        }

    }
}

希尔排序

简单解释：
希尔排序是插入排序的改进版，我们理解一个叫做下标差的的东西，也就是下面那个图中的增量d，初始下标差为arr.length/2，然后继续/2，对在同一下标差（相当于把这几个数单独拿出来了）的若干个数进行插入排序即可。

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: ShellSort
 * @Description: 希尔排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:39
 */
public class ShellSort {

    public static void shellSort(int[] arr) {
        shellSort(arr,true);
    }

    public static void shellSort(int[] arr,boolean ascending) {

        for(int d = arr.length/2;d>0;d/=2){

            for(int i=d;i< arr.length;i++){
                int temp = arr[i];
                int j=0;
                for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){
                    arr[j+d]=arr[j];
                }
                arr[j+d] = temp;
            }
        }

    }
}

计数排序

简单解释：
这个排序算法看名字也很好理解，就是就是额外找个数组来计数，然后在这个数组从小到大或从大到小把数取出来即可。

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: CountSort
 * @Description: 计数排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 11:31
 */
public class CountSort {

    public static void countSort(int[]arr){
        countSort(arr,true);
    }

    public static void countSort(int[]arr,boolean ascending){
        int d,min=arr[0],max=arr[0];

        //找出最大、最小值
        for(int i=0;i< arr.length;i++){
            if(arr[i]<min){
                min =arr[i];
            }
            if(arr[i]>max){
                max = arr[i];
            }
        }

        //建立一个用于计数的数组
        d = min;
        int[] count_map = new int[max-min+1];
        for(int i=0;i< arr.length;i++){
            count_map[arr[i]-d]++;
        }

        int k =0;
        if(ascending){
            for(int i=0;i< arr.length;){
                if(count_map[k]>0){
                    arr[i] = k+d;
                    i++;
                    count_map[k]--;
                }else
                    k++;
            }
        }else {
            for(int i=arr.length-1;i>=0;){
                if(count_map[k]>0){
                    arr[i] = k+d;
                    i--;
                    count_map[k]--;
                }else
                    k++;
            }
        }

    }
}

桶排序

简单解释：
就是把一个数组分成几个桶（其实是几个区间，从小到大或从大到小的几个区间）装，然后让每个桶（区间）有序，然后取出来放一起就可以了，相当于把几个有序的段拿出来放一起，自然还是有序的，当然需要是按照区间的顺序拿了。

完整代码：

package com.keafmd.Sequence;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Keafmd
 *
 * @ClassName: BucketSort
 * @Description: 桶排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 13:32
 */
public class BucketSort {

    public static void bucketSort(int[] arr){
        bucketSort(arr,true);
    }

    public static void bucketSort(int[] arr,boolean ascending){
        if(arr==null||arr.length==0){
            return;
        }
        //计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<arr.length;i++){
            max = Math.max(arr[i],max);
            min = Math.min(arr[i],min);
        }

        //计算桶的数量
        int bucketNUm = (max-min)/ arr.length+1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNUm);
        for(int i=0;i<bucketNUm;i++){
            bucketArr.add(new ArrayList<>());
        }

        //将每个元素放入桶中
        for(int i=0;i<arr.length;i++){
            int num = (arr[i]-min)/ (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        //对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            //用系统的排序，速度肯定没话说
            Collections.sort(bucketArr.get(i));
        }

        //将桶中元素赋值到原序列
        int index;
        if(ascending){
            index=0;
        }else{
            index=arr.length-1;
        }

        for(int i=0;i<bucketArr.size();i++){
            for(int j= 0;j<bucketArr.get(i).size();j++){
                arr[index] = bucketArr.get(i).get(j);
                if(ascending){
                    index++;
                }else{
                    index--;
                }
            }

        }

    }
}

基数排序

简单解释：
首先说一下，我发现好多人写的基数排序只能排序正整数，其实只要处理下就可以排序含有负数的了，就是我们排序前先把所有的数整体变大（就是减上最小的负数，也就是加了），都变成正数，然后排序好之后，在减下来（加上最小的负数，也就减了）就好了。
基数排序就是按数位排序可分为LSD（从最低位[也就是个位]开始排序）和MSD（从最高位开始排序），下面写的事LSD基数排序。
基数排序就是把数按位考虑，让后我们一位数只能是[0，9]，就是我们在考虑某位（个位、百位· · ·）的时候就只看这个位的数，放到在[0，9]相应的位置，然后顺序取出，最后再按其它位这样操作（上面说了要不从低位开始到高位，要不就是从高位到低位）

完整代码：

package com.keafmd.Sequence;

/**
 * Keafmd
 *
 * @ClassName: RadixSort
 * @Description: 基数排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 14:32
 */
public class RadixSort {
    public static void radixSort(int[] arr){
        radixSort(arr,true);
    }
    public static void radixSort(int[]arr,boolean ascending){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        //求出最大值、最小值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        if (min<0) {	//如果最小值小于0，那么把每个数都减去最小值，这样可以保证最小的数是0
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
            max -= min; //max也要处理！
        }
        //很巧妙求出最大的数有多少位
        int maxLength = (max+"").length();
        int[][] bucket = new int[10][arr.length]; //一个二维数组，一维代表0到9，二维存放符合数
        int[] bucketElementCount = new int[10]; // 用于记录0到9某位存在数字的个数
        for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //个位 十位 百位 这样遍历
            for (int j = 0; j < arr.length ; j++) {
                int value = arr[j]/n % 10;
                bucket[value][bucketElementCount[value]] = arr[j];
                bucketElementCount[value]++;
            }

            //升序
            if(ascending) {
                int index = 0;
                //从左到右，从下到上取出每个数
                for (int j = 0; j < bucketElementCount.length; j++) {
                    if (bucketElementCount[j] != 0) {
                        for (int k = 0; k < bucketElementCount[j]; k++) {
                            arr[index] = bucket[j][k];
                            index++;
                        }
                    }
                    bucketElementCount[j] = 0;
                }
            }else { // 降序
                int index=0;
                //从右到左，从下到上取出每个数
                for (int j = bucketElementCount.length-1; j >=0; j--) {
                    if (bucketElementCount[j] != 0) {
                        for (int k = 0; k <bucketElementCount[j]; k++) {
                            arr[index] = bucket[j][k];
                            index++;
                        }
                    }
                    bucketElementCount[j] = 0;
                }
            }


            /*for (int i1 = 0; i1 < arr.length; i1++) {
                System.out.print(arr[i1]+" ");
            }
            System.out.println();*/



        }
        if (min<0){
            for (int i = 0; i < arr.length ; i++) {
                arr[i] += min;
            }
        }

    }
}

完整测试类

package com.keafmd.Sequence;

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * Keafmd
 *
 * @ClassName: Sort
 * @Description: 十大排序算法测试类
 * @author: 牛哄哄的柯南
 * @date: 2021-06-16 21:27
 */
public class Sort {


    public static void main(String[] args) {

        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
//        int[] nums = {12, 43,56,42,26,11};
        int[] temparr;

        //利用系统Collections.sort方法进行对比

        //将int数组转换为Integer数组
        //1、先将int数组转换为数值流
        temparr = nums.clone();
        IntStream stream = Arrays.stream(temparr);
        //2、流中的元素全部装箱，转换为流 ---->int转为Integer
        Stream<Integer> integerStream = stream.boxed();
        //3、将流转换为数组
        Integer[] integers = integerStream.toArray(Integer[]::new);
        //把数组转为List
        List<Integer> tempList = new ArrayList<>(Arrays.asList(integers));
        //使用Collections.sort()排序
        System.out.println("使用系统的Collections.sort()的对比:");

        //Collections.sort
        Collections.sort(tempList, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
                //return o2-o1;
            }
        });

        //tempList.sort 也可以排序
       /* tempList.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //return o1-o2;
                return o2-o1;
            }
        });*/

        //遍历输出结果
        for (Integer integer : tempList) {
            System.out.print(integer+" ");
        }

        System.out.println();

        //测试冒泡排序
        System.out.println("测试冒泡排序:");
        temparr = nums.clone();

        BubbleSort.bubbleSort(temparr);

        //降序
        //BubbleSort.bubbleSort(temparr,false);

        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试快速排序
        System.out.println("测试快速排序:");
        temparr = nums.clone();
        QuickSort.quickSort(temparr);
        //QuickSort.quickSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试直接选择排序
        System.out.println("测试直接选择排序:");
        temparr = nums.clone();
        SelectSort.selectSort(temparr);
        //SelectSort.selectSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试堆排序
        System.out.println("测试堆排序:");
        temparr = nums.clone();
        HeapSort.heapSort(temparr);
        //HeapSort.heapSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试归并排序
        System.out.println("测试归并排序:");
        temparr = nums.clone();
        MergeSort.mergeSort(temparr);
        //MergeSort.mergeSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试插入排序
        System.out.println("测试插入排序:");
        temparr = nums.clone();
        StraghtInsertSort.straghtInsertSort(temparr);
        //StraghtInsertSort.straghtInsertSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();


        //测试希尔排序
        System.out.println("测试希尔排序:");
        temparr = nums.clone();
        ShellSort.shellSort(temparr);
        //ShellSort.shellSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();


        //测试计数排序
        System.out.println("测试计数排序:");
        temparr = nums.clone();
        CountSort.countSort(temparr);
        //CountSort.countSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();


        //测试桶排序
        System.out.println("测试桶排序:");
        temparr = nums.clone();
        BucketSort.bucketSort(temparr);
        //BucketSort.bucketSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

        //测试基数排序
        System.out.println("测试基数排序:");
        temparr = nums.clone();
        RadixSort.radixSort(temparr);
        //RadixSort.radixSort(temparr,false);
        for (int i = 0; i < temparr.length; i++) {
            System.out.print(temparr[i] + " ");
        }
        System.out.println();

    }

}

每天进步一点点！
不进则退！

版权声明：
原创博主：牛哄哄的柯南
博主原文链接：https://keafmd.blog.csdn.net/

看完如果对你有帮助，感谢点赞支持！
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它[哈哈]

加油！

共同努力！

Keafmd

本次内容大纲：

注：下列八大排序的代码均以排升序为例。

直接插入排序

动图演示：

 插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。
基本思想：
 在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。

 但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

代码：

//插入排序
void InsertSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int end = i;//记录有序序列的最后一个元素的下标
		int tmp = a[end + 1];//待插入的元素
		while (end >= 0)
		{
			if (tmp < a[end])//还需继续比较
			{
				a[end + 1] = a[end];
				end--;
			}
			else//找到应插入的位置
			{
				break;
			}
		}
		a[end + 1] = tmp;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）。
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）。
	}
}

时间复杂度：$O(N^2)$  空间复杂度：$O(1)$

希尔排序

动图演示：

 希尔排序是按其设计者希尔的名字命名的，该算法由希尔1959年公布。希尔可以说是一个脑洞非常大的人，他对普通插入排序的时间复杂度进行分析，得出了以下结论：
 1.普通插入排序的时间复杂度最坏情况下为O(N²)，此时待排序列为逆序，或者说接近逆序。
 2.普通插入排序的时间复杂度最好情况下为O(N)，此时待排序列为升序，或者说接近升序。

于是希尔就想：若是能先将待排序列进行一次预排序，使待排序列接近有序（接近我们想要的顺序），然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N)，那么只要控制预排序阶段的时间复杂度不超过O(N²)，那么整体的时间复杂度就比直接插入排序的时间复杂度低了。

希尔排序，又称缩小增量法。其基本思想是：
 1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
 2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

问题：为什么要让gap由大到小呢？
answer：gap越大，数据挪动得越快；gap越小，数据挪动得越慢。前期让gap较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。

注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。

举个例子分析一下：
 现在我们用希尔排序对该序列进行排序。

 我们用序列长度的一半作为第一次排序时gap的值，此时相隔距离为5的元素被分为一组（共分了5组，每组有2个元素），然后分别对每一组进行直接插入排序。

 gap的值折半，此时相隔距离为2的元素被分为一组（共分了2组，每组有5个元素），然后再分别对每一组进行直接插入排序。

 gap的值再次减半，此时gap减为1，即整个序列被分为一组，进行一次直接插入排序。

 该题中，前两趟就是希尔排序的预排序，最后一趟就是希尔排序的直接插入排序。

代码：

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;//gap折半
		int i = 0;
		//进行一趟排序
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

时间复杂度：$O(NlogN)$  空间复杂度：$O(1)$

平均时间复杂度：$O(N^{1.3})$

选择排序

动图演示：

 选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

代码：

//选择排序(一次选一个数)
void SelectSort(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
	{
		int start = i;
		int min = start;//记录最小元素的下标
		while (start < n)
		{
			if (a[start] < a[min])
				min = start;//最小值的下标更新
			start++;
		}
		Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
	}
}

时间复杂度：$O(N^2)$  空间复杂度：$O(1)$

 实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

代码：

//选择排序(一次选两个数)
void SelectSort(int* a, int n)
{
	int left = 0;//记录参与该趟选择排序的第一个元素的下标
	int right = n - 1;//记录参与该趟选择排序的最后一个元素的下标
	while (left < right)
	{
		int minIndex = left;//记录最小元素的下标
		int maxIndex = left;//记录最大元素的下标
		int i = 0;
		//找出最大值及最小值的下标
		for (i = left; i <= right; i++)
		{
			if (a[i] < a[minIndex])
				minIndex = i;
			if (a[i]>a[maxIndex])
				maxIndex = i;
		}
		//将最大值和最小值放在序列开头和末尾
		Swap(&a[minIndex], &a[left]);
		if (left == maxIndex)
		{
			maxIndex = minIndex;//防止最大值位于序列开头，被最小值交换
		}
		Swap(&a[maxIndex], &a[right]);
		left++;
		right--;
	}
}

时间复杂度：$O(N^2)$  空间复杂度：$O(1)$

堆排序

 要学习堆排序，首先要学习堆的向下调整算法，因为要用堆排序，你首先得建堆，而建堆需要执行多次堆的向下调整算法。

堆的向下调整算法（使用前提）：
 若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
 若想将其调整为大堆，那么根结点的左右子树必须都为大堆。

向下调整算法的基本思想（以建大堆为例）：
 1.从根结点处开始，选出左右孩子中值较大的孩子。
 2.让大的孩子与其父亲进行比较。
 若大的孩子比父亲还大，则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
 若大的孩子比父亲小，则不需处理了，调整完成，整个树已经是大堆了。

图片示例：

堆的向下调整算法代码：

//堆的向下调整算法
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;//假设左孩子较大
	while (child < n)
	{
		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在，并且比左孩子大
		{
			child++;//左右孩子的较大值
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}

 使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log₂(N+1)（N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。

 上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？
 答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

建堆代码：

	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}

那么建堆的时间复杂度又是多少呢？
 当结点数无穷大时，完全二叉树与其层数相同的满二叉树相比较来说，它们相差的结点数可以忽略不计，所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。

我们计算建堆过程中总共交换的次数：
$T(n)=1\times (h-1)+2\times (h-2)+...+2^{h-3}\times 2+2^{h-2}\times 1$
两边同时乘2得：
$2T(n)=2\times (h-1)+2^2\times (h-2)+...+2^{h-2}\times 2+2^{h-1}\times 1$
两式相减得：
$T(n)=1-h+2^1+2^2+...+2^{h-2}+2^{h-1}$
运用等比数列求和得：
$T(n)=2^h-h-1$
由二叉树的性质，有$N=2^h-1$和$h={\log }_2(N+1)$，于是
$T(n)=N-{\log }_2(N+1)$
用大O的渐进表示法：
$T(n)=O(N)$

总结一下：
 堆的向下调整算法的时间复杂度：$T(n)=O(\log N)$。
 建堆的时间复杂度：$T(n)=O(N)$。

那么堆建好后，如何进行堆排序呢？
步骤如下：
 1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。
 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

堆排序代码：

//堆排序
void HeapSort(int* a, int n)
{
	//排升序，建大堆
	//从第一个非叶子结点开始向下调整，一直到根
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;//记录堆的最后一个数据的下标
	while (end)
	{
		Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换
		AdjustDown(a, end, 0);//对根进行一次向下调整
		end--;//堆的最后一个数据的下标减一
	}
}

时间复杂度：$O(NlogN)$  空间复杂度：$O(1)$

冒泡排序

动图演示：

冒泡排序，该排序的命名非常形象，即一个个将气泡冒出。冒泡排序一趟冒出一个最大（或最小）值。

代码：

//冒泡排序
void BubbleSort(int* a, int n)
{
	int end = 0;
	for (end = n - 1; end >= 0; end--)
	{
		int exchange = 0;//记录该趟冒泡排序是否进行过交换
		int i = 0;
		for (i = 0; i < end; i++)
		{
			if (a[i]>a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				exchange = 1;
			}
		}
		if (exchange == 0)//该趟冒泡排序没有进行过交换，已有序
			break;
	}
}

时间复杂度：$O(N^2)$  空间复杂度：$O(1)$

快速排序

快速排序是公认的排序之王，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法，其基本思想为：
 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

对于如何按照基准值将待排序列分为两子序列，常见的方式有：
 1、Hoare版本
 2、挖坑法
 3、前后指针法

递归实现

Hoare版本

单趟的动图演示：

Hoare版本的单趟排序的基本步骤如下：
 1、选出一个key，一般是最左边或是最右边的。
 2、定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为key，则需要L先走）。
 3、在走的过程中，若R遇到小于key的数，则停下，L开始走，直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

 经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。

 然后我们在将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的。

代码：

//快速排序（Hoare版本）
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
		return;
		
	int left = begin;//L
	int right = end;//R
	int keyi = left;//key的下标
	while (left < right)
	{
		//right先走，找小
		while (left < right&&a[right] >= a[keyi])
		{
			right--;
		}
		//left后走，找大
		while (left < right&&a[left] <= a[keyi])
		{
			left++;
		}
		if (left < right)//交换left和right的值
		{
			Swap(&a[left], &a[right]);
		}
	}
	int meeti = left;//L和R的相遇点
	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值

	QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度：$O(NlogN)$

挖坑法

单趟的动图演示：

挖坑法的单趟排序的基本步骤如下：
 1、选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
 2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）。
 3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

 经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。

 然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

代码：

//快速排序（挖坑法）
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
		return;

	int left = begin;//L
	int right = end;//R
	int key = a[left];//在最左边形成一个坑位
	while (left < right)
	{
		//right向左，找小
		while (left < right&&a[right] >= key)
		{
			right--;
		}
		//填坑
		a[left] = a[right];
		//left向右，找大
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		//填坑
		a[right] = a[left];
	}
	int meeti = left;//L和R的相遇点
	a[meeti] = key;//将key抛入坑位

	QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度：$O(NlogN)$

前后指针法

单趟的动图演示：

前后指针法的单趟排序的基本步骤如下：
 1、选出一个key，一般是最左边或是最右边的。
 2、起始时，prev指针指向序列开头，cur指针指向prev+1。
 3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可。

 经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

 然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

代码：

//快速排序（前后指针法）
void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
		return;

	//三数取中
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midIndex]);

	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)//当cur未越界时继续
	{
		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	int meeti = prev;//cur越界时，prev的位置
	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容

	QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度：$O(NlogN)$

非递归实现

 当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。
 于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序，在函数内部调用单趟排序的函数即可。

Hoare版本

Hoare版本的单趟排序代码：

//Hoare版本（单趟排序）
int PartSort1(int* a, int left, int right)
{
	int keyi = left;//key的下标
	while (left < right)
	{
		//right走，找小
		while (left < right&&a[right] >= a[keyi])
		{
			right--;
		}
		//left先走，找大
		while (left < right&&a[left] <= a[keyi])
		{
			left++;
		}
		if (left < right)
		{
			Swap(&a[left], &a[right]);//交换left和right的值
		}
	}
	int meeti = left;//L和R的相遇点
	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
	return meeti;//返回相遇点，即key的当前位置
}

挖坑法

挖坑法的单趟排序代码：

//挖坑法（单趟排序）
int PartSort2(int* a, int left, int right)
{
	int key = a[left];//在最左边形成一个坑位
	while (left < right)
	{
		//right向左，找小
		while (left < right&&a[right] >= key)
		{
			right--;
		}
		//填坑
		a[left] = a[right];
		//left向右，找大
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		//填坑
		a[right] = a[left];
	}
	int meeti = left;//L和R的相遇点
	a[meeti] = key;//将key抛入坑位
	return meeti;//返回key的当前位置
}

前后指针法

前后指针法的单趟排序代码：

//前后指针法（单趟排序）
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)//当cur未越界时继续
	{
		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	int meeti = prev;//cur越界时，prev的位置
	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
	return meeti;//返回key的当前位置
}

快速排序的非递归算法基本思路：
 1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
 2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
 3、反复执行步骤2，直到栈为空为止。

代码：

//快速排序（非递归实现）
void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;//创建栈
	StackInit(&st);//初始化栈
	StackPush(&st, begin);//待排序列的L
	StackPush(&st, end);//待排序列的R
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);//读取R
		StackPop(&st);//出栈
		int left = StackTop(&st);//读取L
		StackPop(&st);//出栈
		//该处调用的是Hoare版本的单趟排序
		int keyi = PartSort1(a, left, right);
		if (left < keyi - 1)//该序列的左序列还需要排序
		{
			StackPush(&st, left);//左序列的L入栈
			StackPush(&st, keyi - 1);//左序列的R入栈
		}
		if (keyi + 1 < right)// 该序列的右序列还需要排序
		{
			StackPush(&st, keyi + 1);//右序列的L入栈
			StackPush(&st, right);//右序列的R入栈
		}
	}
	StackDestroy(&st);//销毁栈
}

时间复杂度：$O(NlogN)$

快速排序的两个优化

三数取中

 快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：

 若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。

 可是谁能保证你每次选取的key都是正中间的那个数呢？当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低：

 可以看到，这种情况下，快速排序的时间复杂度退化为O(N²)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：
 三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码：

//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left]>a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
}

注意：当大小居中的数不在序列的最左或是最右端时，我们不是就以居中数的位置作为key的位置，而是将key的值与最左端的值进行交换，这样key就还是位于最左端了，所写代码就无需改变，而只需在单趟排序代码开头加上以下两句代码即可：

	int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标
	Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换
	//以下代码保持不变...

小区间优化

 我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
 为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。

代码示例：

//优化后的快速排序
void QuickSort0(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时，不需要进行操作
		return;

	if (end - begin + 1 > 20)//可自行调整
	{
		//可调用快速排序的单趟排序三种中的任意一种
		//int keyi = PartSort1(a, begin, end);
		//int keyi = PartSort2(a, begin, end);
		int keyi = PartSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);//key的左序列进行此操作
		QuickSort(a, keyi + 1, end);//key的右序列进行此操作
	}
	else
	{
		//HeapSort(a, end - begin + 1);
		ShellSort(a, end - begin + 1);//当序列长度小于等于20时，使用希尔排序
	}
}

归并排序

动图演示：

 归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

 相信大家都知道如何将两个有序序列合为一个有序序列吧：

 那么如何得到有序的子序列呢？当序列分解到只有一个元素或是没有元素时，就可以认为是有序了，这时分解就结束了，开始合并：

递归实现

 归并排序，从其思想上看就很适合使用递归来实现，并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组。

代码：

//归并排序（子函数）
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时，不需要再分解
	{
		return;
	}
	int mid = left + (right - left) / 2;//中间下标
	_MergeSort(a, left, mid, tmp);//对左序列进行归并
	_MergeSort(a, mid + 1, right, tmp);//对右序列进行归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	//将两段子区间进行归并，归并结果放在tmp中
	int i = left;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//将较小的数据优先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//归并完后，拷贝回原数组
	int j = 0;
	for (j = left; j <= right; j++)
		a[j] = tmp[j];
}
//归并排序（主体函数）
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//归并排序
	free(tmp);//释放空间
}

时间复杂度：$O(NlogN)$  空间复杂度：$O(N)$

非递归实现

 归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：

 当然，以上例子是一个待排序列长度比较特殊的例子，我们若是想写出一个广泛适用的程序，必定需要考虑到某些极端情况：
情况一：
 当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够gap个，这时我们需要在合并序列时，对第二个小区间的边界进行控制。

情况二：
 当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。

情况三：
 当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够gap个，此时也不需要对该小组进行合并。（可与情况二归为一类）

 只要把控好这三种特殊情况，写出归并排序的非递归算法便轻而易举了。

代码：

//归并排序（子函数）
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
	int j = begin1;
	//将两段子区间进行归并，归并结果放在tmp中
	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2)
	{
		//将较小的数据优先放入tmp
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
	//归并完后，拷贝回原数组
	for (; j <= end2; j++)
		a[j] = tmp[j];
}
//归并排序（主体函数）
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间，用于辅助合并序列
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	int gap = 1;//需合并的子序列中元素的个数
	while (gap < n)
	{
		int i = 0;
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个，此时不需要对该小组进行合并
				break;
			if (end2 >= n)//最后一组的第二个小区间不够gap个，则第二个小区间的后界变为数组的后界
				end2 = n - 1;
			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
		}
		gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
	}
	free(tmp);//释放空间
}

时间复杂度：$O(NlogN)$  空间复杂度：$O(N)$

外排序

首先，我先说明一下什么是内排序，什么是外排序：
 内排序：数据量相对少一些，可以放到内存中进行排序。
 外排序：数据量较大，内存中放不下，数据只能放到磁盘文件中，需要排序。

 上面介绍的排序算法均是在内存中进行的，对于数据量庞大的序列，上面介绍的排序算法都束手无策，而归并排序却能胜任这种海量数据的排序。

 假设现在有10亿个整数（4GB）存放在文件A中，需要我们进行排序，而内存一次只能提供512MB空间，归并排序解决该问题的基本思路如下：
 1、每次从文件A中读取八分之一，即512MB到内存中进行排序（内排序），并将排序结果写入到一个文件中，然后再读取八分之一，重复这个过程。那么最终会生成8个各自有序的小文件（A1~A8）。
 2、对生成的8个小文件进行11合并，最终8个文件被合成为4个，然后再11合并，就变成2个文件了，最后再进行一次11合并，就变成1个有序文件了。

注意：这里将两个文件进行11合并，并不是先将两个文件读入内存然后进行合并，因为内存装不下。这里的11合并是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另一个文件中去，那么此时这个文件又是一个有序的文件了。

当然，你也可以这样合并文件：

外排序代码示例：

//将file1文件和file2文件中的数据归并到mfile文件中
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
	FILE* fout1 = fopen(file1, "r");//打开file1文件
	if (fout1 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fout2 = fopen(file2, "r");//打开file2文件
	if (fout2 == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	FILE* fin = fopen(mfile, "w");//打开mfile文件
	if (fin == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}

	int num1, num2;
	int ret1 = fscanf(fout1, "%d\n", &num1);//读取file1文件中的数据
	int ret2 = fscanf(fout2, "%d\n", &num2);//读取file2文件中的数据
	while (ret1 != EOF && ret2 != EOF)
	{
		//将读取到的较小值写入到mfile文件中，继续从file1和file2中读取数据进行比较
		if (num1 < num2)
		{
			fprintf(fin, "%d\n", num1);
			ret1 = fscanf(fout1, "%d\n", &num1);
		}
		else
		{
			fprintf(fin, "%d\n", num2);
			ret2 = fscanf(fout2, "%d\n", &num2);
		}
	}
	//将file1文件中未读取完的数据写入文件mfile中
	while (ret1 != EOF)
	{
		fprintf(fin, "%d\n", num1);
		ret1 = fscanf(fout1, "%d\n", &num1);
	}
	//将file2文件中未读取完的数据写入文件mfile中
	while (ret2 != EOF)
	{
		fprintf(fin, "%d\n", num2);
		ret2 = fscanf(fout2, "%d\n", &num2);
	}
	fclose(fout1);//关闭file1文件
	fclose(fout2);//关闭file2文件
	fclose(fin);//关闭mfile文件
}
//将文件中的数据进行排序
void MergeSortFile(const char* file)
{
	FILE* fout = fopen(file, "r");//打开文件
	if (fout == NULL)
	{
		printf("打开文件失败\n");
		exit(-1);
	}
	// 分割成一段一段数据，内存排序后写到小文件中
	int n = 10;//一次读取10个数据进行内排序
	int a[10];//读取数据放到数组中，准备进行内排序
	int i = 0;
	int num = 0;
	char subfile[20];//文件名字符串
	int filei = 1;//储存第filei组内排序后的数据的文件的文件名

	memset(a, 0, sizeof(int)*n);//将数组a的空间置0
	while (fscanf(fout, "%d\n", &num) != EOF)//从文件中读取数据
	{
		if (i < n - 1)//读取前9个数据
		{
			a[i++] = num;
		}
		else//读取第10个数据
		{
			a[i] = num;
			QuickSort(a, 0, n - 1);//将这10个数据进行快速排序
			sprintf(subfile, "%d", filei++);//将储存第filei组内排序后的数据的文件的文件名命名为filei
			FILE* fin = fopen(subfile, "w");//创建一个以字符串subfile[20]为名字的文件并打开
			if (fin == NULL)
			{
				printf("打开文件失败\n");
				exit(-1);
			}
			//将内排序排好的数据写入到subfile文件中
			for (int i = 0; i < n; i++)
			{
				fprintf(fin, "%d\n", a[i]);
			}
			fclose(fin);//关闭subfile文件

			i = 0;
			memset(a, 0, sizeof(int)*n);//将a数组内存置0，准备再次读取10个数据进行内排序
		}
	}
	// 利用互相归并到文件，实现整体有序
	char mfile[100] = "12";//归并后文件的文件名
	char file1[100] = "1";//待归并的第一个文件的文件名
	char file2[100] = "2";//待归并的第二个文件的文件名
	for (int i = 2; i <= n; ++i)
	{
		//将file1文件和file2文件中的数据归并到mfile文件中
		_MergeFile(file1, file2, mfile);

		strcpy(file1, mfile);//下一次待归并的第一个文件就是上一次归并好的文件
		sprintf(file2, "%d", i + 1);//上一次待归并的第二个文件的文件名加一，就是下一次待归并的第二个文件的文件名
		sprintf(mfile, "%s%d", mfile, i + 1);//下一次归并后文件的文件名
	}

	fclose(fout);//关闭文件
}
//主函数
int main()
{
	MergeSortFile("Sort.txt");//将Sort.txt文件中的数据进行排序
	return 0;
}

注：代码中使用的是第二种文件合并的方式。

计数排序

 计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

举个例子：

 上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，但这样会造成空间浪费。例如，我们要将数组：1020,1021,1018，进行排序，难道我们要开辟1022个整型空间吗？
 若是使用计数排序，我们应该使用相对映射，简单来说，数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组：1020,1021,1018，我们就只需要开辟用于储存4个整型的空间大小了，此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。

总结：
 绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
 相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。

注：计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。

代码：

//计数排序
void CountSort(int* a, int n)
{
	int min = a[0];//记录数组中的最小值
	int max = a[0];//记录数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
	int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//统计相同元素出现次数（相对映射）
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int i = 0;
	//根据统计结果将序列回收到原来的序列中
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
	free(count);//释放空间
}

时间复杂度：$O(N+range)$  空间复杂度：$O(range)$