常用排序算法

一、排序的概念与应用

1.排序的概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

我们在淘宝中寻找商品时，在左上有四种排序方式：综合、信用、价格降序、价格升序。这四种方式都可以把搜索到的数据进行排序，将更符合你需要的商品放在前面。

头一个就是杨村糕干hhhh

再比如说报志愿的时候，我们要考虑学校排名、专业排名、学费高低排名……这些大学的信息很多，通过排序就可以更好地反映大学或者专业的好坏程度，帮助你做出更好的选择。

河北工业大学，河北人永远的痛……

2.常见的排序算法

排序算法主要包括：插入排序、选择排序、交换排序、归并排序

插入排序包括：直接插入排序、希尔排序

选择排序包括：选择排序、堆排序

交换排序包括：冒泡排序、快速排序

二、插入排序

1.概念介绍

void InsertSort(int* a, int n);

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

首先拿到一个数组后，我们认为首个元素是有序的，后面的对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，将每一个未排序的数据插入合适的位置就完成了插入排序。

插入排序在实现上，通常在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

 2.代码实现

我们的代码都是先写单趟的排序，然后再写整个的循环。

void InsertSort(int* a,int n)//a为待排序数组，n为数组的元素个数
{
    int end;//用end储存有序序列的尾下标，此时暂时不需要指出end是什么值
    int temp = a[end+1];//储存无序的首元素
    while (end >= 0)//最多插到下标为0处
    {
        if (temp < a[end])
        {
            a[end+1] = a[end];//把前面的数据挪到后面
            end--;//继续向前找小数据      
        }
        else
            break;
    }
    a[end+1] = temp;
    //一方面，找到比自己小的元素就插到后一位
    //另一方面，在end等于0依旧比temp大的时候，此时end等于-1，end+1又回到了0
}

这个单趟排序需要将除第一个以外的所有元素进行排列，所以循环进行元素个数减一次；最开始排的元素应该是第二个元素，end+1最初等于1，故end从0开始。

//直接插入排序
void InsertSort(int* a,int n)//a为待排序数组，n为数组的元素个数
{
    int i = 0;
    for (i=0; i-1; i++)
    {
        int end = i;//用end储存有序序列的尾下标，用i控制end
        int temp = a[end+1];
        while (end >= 0)
        {
            if (temp < a[end])
            {
                a[end+1] = a[end];
                end--;        
            }
            else
                break;
        }
        a[end+1] = temp;
    }
}

三、希尔排序

1.概念介绍

void ShellSort(int* a, int n);

时间复杂度：O(N^1.3)（希尔排序的时间复杂度很难计算，但是根据统计数据大概在N的1.3次方左右）

简单地说，希尔排序是插入排序的优化版本，这个排序比较难懂，但是时间复杂度低，是可以与堆排序一较高下的优质算法。

希尔排序需要一个预排序操作，而预排序就是对数组的全部元素进行分组，然后各组的元素进行插入排序。此时我们需要一个关键变量gap，这个gap是数组元素划分间隔的标准，我们先假定gap为3，观察预排序的过程。

预排序可以让大数据更快地到达尾端，小数据更快地到达头部，让整个数组相对有序。

聪明如你可能已经想到了，当这个gap等于1时就是直接插入排序。我们需要做的就是让gap不断缩小到1就可以完成这个数组的排序了。但最后直接排序的数组已经相当有序了，所以相比插入排序它的效率会高很多。

2.代码实现

老样子，先写单趟插入排序，然后通过循环改为一组元素的预排序。

void ShellSort(int* a, int n)
{
    int gap;//先不指定值
    int i = 0;//完全一样的思路，不过加一减一改成了加减gap
    for (i=0; i
    {
        int end = i;
        int temp = a[end+gap];
        while (end>=0)
        {
            if(temp < a[end])
            {
                a[end] = a[end+gap];
                end-=gap;        
            }
            else
                break;    
        }     
    }
}

然后再次改为对各组元素插入排序，各组元素的开头元素从0到gap-1，尾元素不超过n

void ShellSort(int* a, int n)
{
    int gap;//先不指定值
    int j = 0;
    for (j=0; j//各组元素的开头元素从0到gap-1，尾元素不超过n
    {
        int i = j;//完全一样的思路，不过加一减一改成了加减gap
        for (i=j; i
        {
            int end = i;
            int temp = a[end+gap];
            while (end>=0)
            {
                if(temp < a[end])
                {
                    a[end] = a[end+gap];
                    end-=gap;        
                }
                else
                    break;    
            }     
        }    
    }
}

最后控制gap的大小，先让gap等于元素个数然后逐渐减小。有两种减小方式，gap=gap/2或者gap=gap/3+1,这两种方法都能保证gap最后必为1，用gap>1的条件判断，gap减小后等于1时进行一次循环就退出了。

void ShellSort(int* a, int n)
{
    int gap = n;
    while(gap>1)
    {
        gap=gap/2;
        int j = 0;
        for (j=0; j//各组元素的开头元素从0到gap-1，尾元素不超过n
        {
            int i = j;//完全一样的思路，不过加一减一改成了加减gap
            for (i=j; i
            {
                int end = i;
                int temp = a[end+gap];
                while (end>=0)
                {
                    if(temp < a[end])
                    {
                        a[end] = a[end+gap];
                        end-=gap;        
                    }
                    else
                        break;    
                }     
            }    
        }   
    }
}

四、选择排序

1.概念介绍

void SelectSort(int* a, int n);

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

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

在我们的实现方法中，会在数组中同时寻找最大值和最小值，最大值放在尾部，最小值放在头部。

2.代码实现

先写单趟

void SelectSort(int* a, int n)
{
    int begin = 0;//起始节点
    int end = n - 1;//尾节点
    int min_i = begin;
    int max_i = end;//保存头尾下标
    int i = 0;
    for (i = begin + 1; i <= end; i++)//通过打擂台的方式找最大值
    {
        if (a[i] > a[max_i])
            max_i = i;
        if (a[i] < a[min_i])
            min_i = i;
    }
    swap(&a[begin], &a[min_i]);//小数据放在前面
    if (max_i == begin)
        max_i = min_i;
    swap(&a[end], &a[max_i]);//大数据放在后面
}

循环起来

// 选择排序
void SelectSort(int* a, int n)
{
    int begin = 0;
    int end = n - 1;
    while (begin < end)//两个下标向中间走
    {
        int min_i = begin;
        int max_i = end;
        int i = 0;
        for (i = begin; i <= end; i++)
        {
            if (a[i] > a[max_i])
                max_i = i;
            if (a[i] < a[min_i])
            min_i = i;
        }
        swap(&a[begin], &a[min_i]);
        if (max_i == begin)//这里有一个小bug，需要修正一下
            max_i = min_i;
        swap(&a[end], &a[max_i]);
        end--;//向前减小返回
        begin++;//向后增大范围
    }
}

五、堆排序

1.概念介绍

void HeapSort(int* a, int n);

时间复杂度：O(NlogN)（log以2为底）

堆排序是一个效率十分高的排序算法，它真的可以说吊打我们学过的冒泡排序，下面介绍一下堆排序的步骤：

（1）建立大堆

你可能会想，为什么不建小堆呢？小堆可以让数组更加有序。

其实不然，小堆确实可以确定头节点为最小值，数组也相对有序。但是，你无法找到次小元素，因为小堆只保证父节点小于子节点，但是你无法判断左右子节点数据的大小。所以，我们通过建立大堆就一定可以在头节点找到最大的元素。

（2）交换首尾元素并让堆的有效数据减一

大堆的头节点一定是最大的元素，那么我们交换最大的数据到最后，它也就在了它最终该在的位置。然后有效数据减一，让整个堆不再管辖最后的这个正确位置的数据

（3）重新建堆

并不是把整个堆清空，而是将你交换到头节点的元素向下调整构成新的堆。

（4）重复上述步骤直到堆中不存在元素即可

整体思路就是堆删除数据的变形

 2.代码实现

代码就直接放在这里了，内部有排序的主函数还有辅助的函数

// 堆排序
typedef struct Heap
{
	int* arr;
	int volume;
	int size;
}HP;
 
void swap(int* p1, int* p2)
{
	int temp = 0;
	temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
 
//向上调整
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])//改
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
 
//向下调整
void AdjustDwon(int* a, int n, int parent)
{
	int need_child = parent * 2 + 1;
	while (need_child < n)
	{
		if (a[need_child] < a[need_child + 1] && need_child + 1 < n)
		{
			need_child++;
		}
		if (a[parent] < a[need_child])
		{
			swap(&a[parent], &a[need_child]);
			parent = need_child;
			need_child = parent * 2 + 1;
		}
		else
			break;
	}
}
 
//主体函数
void HeapSort(int* a, int n)
{
	HP s;
	HP* p = &s;
	p->arr = (int*)malloc(n*sizeof(int));
	p->size = 0;
	p->volume = n;
	int i = 0;
	for (i = 0; i < n; i++)
	{
		p->arr[p->size] = a[i];
		p->size++;
		AdjustUp(p->arr, p->size - 1);
	}
	for (i = 0; i < p->size; i++)
	{
		swap(&p->arr[0], &p->arr[p->size - 1 - i]);
		AdjustDwon(p->arr, p->size - i - 1, 0);
	}
	for (i = 0; i < n; i++)
	{
		a[i] = p->arr[i];
	}
	free(p->arr);
	p->size = 0;
	p->volume = 0;
}

六、冒泡排序

1.概念介绍

void BubbleSort(int* a, int n);

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

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

 2.代码实现

// 冒泡排序
void BubbleSort(int* a, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int j = 0;
        for (j = 0; j < n - 1 - i; j++)
        {
            if (a[j + 1] < a[j])
                swap(&a[j + 1], &a[j]);
        }
    }
}

七、快速排序

时间复杂度：O(NlogN)（log以2为底）

1.快速排序——霍尔方法

（1）概念介绍

int PartSort1(int* a, int left, int right);

void QuickSort1(int* a, int begin, int end);

霍尔法是快速排序最早的实现方法也是三种方法中最复杂的。

首先，讲单趟排序：

• 霍尔法中需要三个整形变量，一个left储存头的下标，一个right储存尾的下标，还有一个key_i储存标准位置的下标，这个标准位置定位在数组的开头。比如说，在下图中left和key_i为0，right为9。
• left向右移动寻找比标准下标对应的值大的元素，right向左寻找比标准下标对应的值小的元素，两个都是找到对应元素就停止。为了保证left与right相遇下标的元素小于标准位置必须让right先走。
• 当left和right都停止移动后，交换两个元素的位置，然后继续寻找直到left和right相遇，相遇后直接将首元素和相遇处的元素交换。
• 首元素与相遇元素交换完成后相应的这个标准位置的值也就放在了正确的位置上。你可能想问，为嘛呢？因为left和right要想相遇left左侧所有元素必须小于这个标准位置，right右侧所有元素必须大于这个标准位置，比如下面的序列标准位置为6，所有比6小的值都在左侧，比6大的都在右侧，数组元素个数固定，那么6肯定在正确位置上。
• 最后返回left与right相遇的下标meet_i用于后续递归

然后，讲递归：

• 我们在完成整个数组的单趟排序操作后，相遇位置的元素已经到了正确的位置，那么我们就可以对该节点左右的区间递归进行同样的排序。
• 上一步返回的meet_i位置的元素已经到达了指定位置，所以我们在meet_i节点处断开，确定左区间为（0,meet_i- 1)，右区间为(meet_i+1,end)，两次排序又会各自返回各自的meet_哦，然后再不断递归划分子区间排序。
• 任何递归代码都需要终止条件，子区间不能再排序有两种情况。第一种是子区间内只有一个元素，也就是left等于right；另一种是子区间不存在，也就是left大于right。

（2）代码实现

在看代码之前还需要小小的解释一下，快速排序的思想虽然对于乱序数组的排序十分有效，但是对于一个接近有序的数组而言，这种排序的时间消耗会大大增加。

为了加快近似有序排序的速度，我们可以设置一个找中间值的函数，让我们的标准位置选取头、中间和尾部三个元素中的中间大的那一个（既不是最大，也不是最小）并交换到头部做key

//霍尔方法————快速排序递归实现
//霍尔法一定要让right先走，才可以保证key小于会和位置的数字
//霍尔法在选取key时有三种方法：
//1.取头或尾，就是begin或者end
//2.随机取一个位置
//3.在头、尾、中间位置的三个数据中找到中间大小的数据
int Getmid(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	//首先以两个下标为整体，第三个下标在前一种，在后一种，其余一种
 
	//left mid right
	//left right mid
	//right left mid
	
	//mid left right
	//mid right left
	//right mid left
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[right] < a[left])
			return left;
		else
			return right;
	}
	else
	{
		if (a[right] > a[left])
			return left;
		else if (a[right] < a[mid])
			return mid;
		else
			return right;
	}
}
 
 
 
int PartSort1(int* a, int left, int right)
{
	int key_i = Getmid(a, left, right);
	while (left < right)
	{
		while (left < right && a[right] >= a[key_i])
			right--;
		while (left < right && a[left] <= a[key_i])
			left++;
		if (left < right)
			swap(&a[left], &a[right]);
	}
	int meet_i = left;
	swap(&a[meet_i], &a[key_i]);
	return meet_i;
}
 
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int key_i = PartSort1(a, begin, end);
	QuickSort1(a, begin, key_i - 1);
	QuickSort1(a, key_i+1, end);
}

2.快速排序——挖坑法

（1）概念介绍

int PartSort2(int* a, int left, int right);

void QuickSort2(int* a, int begin, int end);

挖坑法相比霍尔法注意的事项较少而且相对简单易懂。

首先，讲单趟排序：

• 挖坑法中需要四个整形变量，一个left储存头的下标，一个right储存尾的下标，一个hole储存坑位的位置，一个key储存标准位置的值（注意不再是下标），这个标准位依旧选定在头部。
• 首先把左侧第一个元素保存起来，形成一个坑位。right左移找小数据，找到后把该元素放到坑位中，坑位也移动到right的位置。然后左侧找大数据同理填补右面的坑位。
• 直到left与right相遇后我们将key填left和right所在的坑位上，返回最后坑位的位置，就完成了单趟排序

递归思路与霍尔法相同

（2）代码实现

//快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int mid = Getmid(a, left, right);
	swap(&a[left], &a[mid]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小的数
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];//右边的数，填补左边的坑位
		hole = right;//更新hole
		//左边找小的数
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];//左边的数，填补右边的坑位
		hole = left;//更新hole
	}
	a[hole] = key;
	return hole;
}
 
void QuickSort2_1(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int key_i = PartSort2(a, begin, end);
	QuickSort2_1(a, begin, key_i - 1);
	QuickSort2_1(a, key_i + 1, end);
}

（3）代码优化

快速排序的递归代码非常近似于二叉树，我们知道二叉树的节点呈指数从上到下增长，所以我们对越小的数组进行排序时排序的次数也越多，最后一层排序甚至占了整个排序过程的一半。

所以，我们可以在对大数组排序时，可以在排序小数组时使用插入排序。（此时的小子区间内的元素已经接近有序，插入排序对于z接近有序的数组排序的效率很高）

这个子数组在八个元素以下就可以使用插入排序。

//快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
	int mid = Getmid(a, left, right);
	swap(&a[left], &a[mid]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小的数
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];//右边的数，填补左边的坑位
		hole = right;//更新hole
		//左边找小的数
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];//左边的数，填补右边的坑位
		hole = left;//更新hole
	}
	a[hole] = key;
	return hole;
}
//优化
void QuickSort2_2(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//由于八个数据排序需要递归三层，而且随着层数变深，需要开辟栈帧排序的次数越多
	//此时数组已经较为有序，对于较为有序的数组适合使用插入排序，从而减少了运行时间
	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int key_i = PartSort2(a, begin, end);
		QuickSort2_2(a, begin, key_i - 1);
		QuickSort2_2(a, key_i + 1, end);
	}
	
}

3.前后指针法

（1）概念介绍

int PartSort3(int* a, int left, int right);

void QuickSort3(int* a, int begin, int end);

首先讲单趟排序：

• 单趟排序需要用到三个整形元素，一个prev指向头节点，一个cur指向第二个节点。虽然不是真正的指针变量，但是也起到了指示位置的作用。还有再用一个整形元素key_i储存标准值的下标。
• prev和cur指针的移动方式：如果cur指向的元素小于标准值，那么prev向前移动一位，然后将prev和cur指向的元素交换，最后cur向前进一位如果cur指向的元素大于标准值，那么只有cur向后移动一位。
• 直到cur指向数组外时，将prev和cur指向的内容交换一下然后返回prev就完成了单趟排序。

 （2）代码实现

//快速排序前后指针法
//包含两个指针——prev和cur
//prev指在最开头，cur指在第二个
//如果cur指向的元素比key_i下标的元素小，那么prev后挪一位，然后交换它们指向的值
//如果cur指向的元素大于等于key_i下标的元素，那么cur直接后挪一位
//直接后挪的操作导致了cur和prev不再是紧密相连的
//此时当cur停下来时prev和cur之间的数据都是大于key_i下标的元素的
//通过交换的方式就可以将大数和小数交换到后面和前面，从而达到局部有序的目的，最后把key_i下标的元素与prev的元素交换
int PartSort3(int* a, int left, int right)
{
	int mid = Getmid(a, left, right);
	swap(&a[mid], &a[left]);
	int key_i = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key_i] && ++prev != cur)//++prev != cur这一句可以防止自己和自己交换
			swap(&a[prev], &a[cur]);
		cur++;
	}
	swap(&a[key_i], &a[prev]);
	return prev;
}
 
void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int key_i = PartSort3(a, begin, end);
	QuickSort3(a, begin, key_i - 1);
	QuickSort3(a, key_i + 1, end);
}

4.快速排序的非递归实现

（1）概念介绍

我们知道递归代码虽然书写简单，但是占用空间大且速度慢。由于栈区空间很小大概只有几M，所以在排序一个大的数组时可能会出现栈溢出的问题。当我们使用非递归实现时，这些问题就都解决了。

非递归代码又需要用到栈，我们通过函数的调用堆栈发现递归的快速排序函数内部最主要的变量就是left与right，所以栈中的内容应该是数组的首尾元素的下标。

注意，如果你先入头下标后入尾下标，那么接收的时候应该先接收尾再接收头。

（2）代码实现

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{
	stack s;
	stack* p = &s;
	initstack(p);
	//入栈头尾两个节点
	stackpush(p, left);
	stackpush(p, right);
 
	while (!stackempty(p))
	{
		//出栈右节点
		int end = stacktop(p);
		stackpop(p);
 
		//出栈左节点
		int begin = stacktop(p);
		stackpop(p);
 
		if (begin >= end)//此时的序列要么是只有一个元素，要么是这个区间根本不存在
		{
			continue;
		}
		//进行排序
		int key_i = PartSort2(a, begin, end);
		//先入右节点，再入左节点
		//入递归右侧区间
		stackpush(p, key_i + 1);
		stackpush(p, end);
		//入递归左侧区间
		stackpush(p, begin);
		stackpush(p, key_i - 1);
	}
	stackdestory(p);
}

八、归并排序

时间复杂度：O(NlogN)（log以2为底）

整体思路：将一个数组沿中间左右分开，如果左侧和右侧数组不都是有序的就继续向下平分，直到找到有序子数组就将上一层合并为有序。两个一个元素的有序数组合并为一个两个元素的有序数组，两个两个元素的有序数组合并为一个四个元素有序数组，两个四个元素的有序数组合并为一个八个元素的有序数组……直到整个数组有序。

1.递归法

（1）概念介绍

void Part_MergeSort(int* a, int begin, int end, int* temp);

void MergeSort(int* a, int n);

递归排序思路：

• 需要定义两个函数Part_MergeSort和 MergeSort，第一个是整体的排序函数，第二个是用于寻找左右有序区间的函数。

• Part_MergeSort先将整个数组平分为两个区间，如果左右区间不都是有序（这里默认为升序）的，那么就继续将左右区间平分，直到找到有序的左右区间。
• 找到有序区间后通过尾插最小值的方式，将元素插入到temp数组中，再覆盖掉原来对应的数组元素。（注意不是把整个temp数组全部覆盖原数组）

然后，讲递归：

• 任何递归都必须有终止的条件，当我们的左右区间只有一个元素时就可以认为这个区间是有序的。
• MergeSort整体函数的设计思路类似于二叉树的后序遍历，先找左侧的有序数组，然后再找右侧的有序数组，同时满足就合并这两个数组。
• 这样一层一层向上合并有序区间一定会包含整个数组。

（2）代码实现

// 归并排序递归实现
//整体思路：将一个数组沿中间左右分开，如果左侧和右侧数组不都是有序的就继续向下平分，直到找到有序子数组就将上一层合并为有序
//两个一个元素的有序数组合并为一个两个元素的有序数组，
//两个两个元素的有序数组合并为一个四个元素有序数组，
//两个四个元素的有序数组合并为一个八个元素的有序数组……
//直到整个数组有序
 
//内部函数用于寻找有序数组
void Part_MergeSort(int* a, int begin, int end, int* temp)
{
	if (begin >= end)
		return;//在子数组只存在单个元素时可以看作是有序的
 
	int mid = begin + (end - begin) / 2;
 
	//左右区间递归找有序
	Part_MergeSort(a, begin, mid,  temp);
	Part_MergeSort(a, mid+1, end, temp);
 
	//找到左右有序之后，通过找小数据尾插的方式让上一级的双区间有序
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin;
 
	//由于在进入这里时，左右区间都已经是有序的（默认升序）
	//所以我们只需要找左右区间的头部值进行比较即可找到最小的元素，然后插入到新建的数组内部即可
	//举个例子
 
	//左：1 4 7 9  右：2 3 5 8 
	//左右区间均为升序，找头部元素左1右2，较小的为1
	//在temp数组中插入1，同时让左侧的子数组缩短
	//左：4 7 9  右：2 3 5 8 
	//找头部元素左4右2，较小的为2
	//在temp数组中插入2，同时让左侧的子数组缩短
	//左：4 7 9  右：3 5 8 
	//找头部元素左4右3，较小的为3
	//在temp数组中插入3，同时让右侧的子数组缩短
	//左：4 7 9  右：5 8
	//……
	//最后得到：
	//左：9  右：
	//在这里我们运行的逻辑是两个数组找较小值，当有一个数组插入完成时就无需继续循环
	//这也是使用&&的理由
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
			temp[i++] = a[begin1++];
		else
			temp[i++] = a[begin2++];
	}
 
	//当代码走到这里时，一定有一个数组完成了插入，然而我们并不能知道哪一个数组内部还存在元素
	//由于内部存在的元素依旧是有序的，这样我们就只需利用两个循环将数据继续拷贝到temp数组中
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}
	//在复制完成后，有序的元素还需要转移到原来的数组中
	memcpy(a+begin, temp+begin, sizeof(int)*(end - begin + 1));
}

2.非递归法

我们之前的递归改非递归往往需要使用某一种数据结构。子曰：“最高端的食材往往需要最简单的做法。”（孔子：我可没说过）这次我们直接使用循环运行程序，在整个程序运行中最主要的还是注意对有序区间始末位置的控制。

（1）概念介绍

归并排序的递归法存在寻找左右区间同时有序的算法，由于单个元素组成的区间默认为有序，那么我们只需要负责合并各个区间就可以了。

我们使用一个gap变量实现左右区间的划分，和前面一样begin1和begin2，end1和end2储存左右区间的节点。

我们需要先控制左节点头的位置，由于gap是左头节点和右头节点下标相差的数据个数用一个for循环就可以了，从0开始每次跳过两个gap但不超过数组元素的下标。

假设左区间的头节点begin1 = j，那么end2 = j + gap - 1, begin2 = j + gap, end2 = j + 2 * gap - 1.

每一层的左右区间依旧用尾插最小数据的方式合并并排为有序。

你可能以为这个程序就已经结束了，呵呵，事情当然不是这样简单的。别忘了这个程序的重头戏：控制左右数组的头尾位置，防止区间越界。

对于四个数据begin1和begin2，end1和end2我们分析一下每一个变量可能的越界情况：

首先，begin1就是j的值，j不会越界，begin1也就不会越界。

其次，end1是有可能越界的，end1越界时不存在右侧区间，也就无从谈起合并了，这时break跳出循环即可。

然后，begin2越界，依旧没有右区间也无从谈起合并，这时依旧break跳出循环。

最后，end2越界，这时右区间存在，可以进行取小插入的操作，但是需要将end2修正到数组的最后一位也就是n-1上。这样就可以合并为有序数组了。

（2）代码实现

void MergeSort(int* a, int n)
{
	int* temp = malloc(n*sizeof(int));
	if (temp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	Part_MergeSort(a, 0, n - 1, temp);
	free(temp);
	temp = NULL;
}
 
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* temp = (int*)malloc(n*sizeof(int));
	if (temp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		int j = 0;
		for (j = 0; j < n; j += 2*gap)
		{
			int begin1 = j;
			int end1 = j + gap - 1;
			int begin2 = j + gap;
			int end2 = j + 2 * gap - 1;
			//()内的数据为有序，两两一组
			//arr:(9) (5)   (6) (8)   (7) (4)   (1) (3)   (2)
			//arr:(5 9) (6 8)   (4 7) (1 3)   (2)
			//arr:(5 6 8 9)   (1 3 4 7)   (2)
			//arr:(5 6 8 9)   (1 3 4 7)   (2)
			// 第一组越界
			if (end1 >= n)
			{
				printf("[%d,%d]", begin1, n - 1);
				break;
			}
 
			// 第二组全部越界
			if (begin2 >= n)
			{
				printf("[%d,%d]", begin1, end1);
				break;
			}
 
			// 第二组部分越界
			if (end2 >= n)
			{
				// 修正一下end2，继续归并
				end2 = n - 1;
			}
 
			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
			int i = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
					temp[i++] = a[begin1++];
				else
					temp[i++] = a[begin2++];
			}
			while (begin1 <= end1)
			{
				temp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[i++] = a[begin2++];
			}
			memcpy(a + j, temp + j, sizeof(int)*(end2 - j + 1));
		}
		gap *= 2;
		printf("\n");
	}
	free(temp);
	temp = NULL;
}

九、计数排序

（1）概念介绍

这个排序是我们学过的唯一一个不需要比较元素大小的排序方式，它的实现方式比较特殊，需要开辟一个数组用于储存各个数据出现的个数，根据每个元素出现的个数直接从头到尾按个数添加对应元素覆盖原数组。

首先，定义max和min为数组头元素，经过一个一个的比较找到数组的最大值和最小值。

开辟一个最大值减最小值大小的数组，a[i]-min为下标的元素储存下标为i的元素出现的个数，这个叫做相对位置数组。

最后按次数插入对应元素即可。

（2）代码实现

// 计数排序
void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	int i = 0;
	for (i = 1; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int* temp = (int*)calloc(max-min+1, (unsigned int)sizeof(int));//calloc可以初始化所有位置为0
	if (temp == NULL)
	{
		perror("malloc fail:");
		return;
	}
	for (i = 0; i < n; i++)
	{
		int data = a[i];
		temp[data - min]++;
	}
	int j = 0;
	for (i = 0; i < max - min + 1; i++)
	{
		while (temp[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(temp);
	temp = NULL;
}

十、所有排序的时间消耗

void InsertSort(int* a, int n);

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

void ShellSort(int* a, int n);

时间复杂度：O(N^1.3)（希尔排序的时间复杂度很难计算，但是根据统计数据大概在N的1.3次方左右）

void SelectSort(int* a, int n);

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

void HeapSort(int* a, int n);

时间复杂度：O(NlogN)（log以2为底）

void BubbleSort(int* a, int n);

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

void QuickSort(int* a, int begin, int end);

时间复杂度：O(NlogN)

void MergeSort(int* a, int n);

时间复杂度：O(NlogN)（log以2为底）

void CountSort(int* a, int n);

时间复杂度：O(N)

 上面是我用各种排序方法排序50000个随机数生成的数组使用的时间

通过长期的使用，我们可以得到下面的结论：

• 插入排序、选择排序、冒泡排序时间复杂度高，虽然逻辑简单便于书写，但是非常不适合海量数据的排序。
• 希尔排序是插入排序的优化，但是对于接近有序的数组就会显得吃力；插入排序对于排序接近有序的数组而言效率很高。
• 堆排序、快速排序、归并排序是效率相当高的算法。非常适合排序大量乱序的元素。
• 快速排序的优化确实能起到一定减少时间消耗的作用，但是并不能将程序的运行时间缩短一个量级（这里排序的数组太小，不容易看出来）
• 计数排序的需要开辟额外的空间，最大值和最小值越接近，开辟的空间也越小，所以计数排序更适合排序元素大小相对接近的数组

结语：排序的种类千千万万，有好的也有不好的，我们都需要了解。在学习完排序后，数据结构的c语言部分也就彻底结束了。