
void BubbleSort(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n-i-1; j++)
		{
			if (arr[j + 1] < arr[j])
			{
				swap(&arr[j + 1], &arr[j]);
			}
		}
	}
}

冒泡排序是通过两两相比来确定大小的排序，如果后面的比前面的大就进行交换。第一层循环是比较的轮数，第二层循环用于在每轮中进行实际的比较和交换操作。n-i-1是因为每一轮比较后，最大的i个数已经在其正确的位置上，所以下一轮不需要再考虑它们。冒泡排序每次都能确定一个位置

为什么是n-i-1而不是n-i，如果要排序的数组有5个元素，也就是n等于5。那么限制条件就是j<5,j最大有可能取到4，但是我们的判断交换的条件是if (arr[j + 1] < arr[j])，如果j取到4，那么j+1就会取到5，此时数组已经越界，程序直接崩溃。

其实也有第二种写法，j直接取最后一个，也就是j=n-1;让arr[j-1]和arr[j]去判断比较是否需要交换次序，这样就不用考虑是否需要减1来防止越界，容错率更好一点。

代码如下


void BubbleSort(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = n-1; j>i; j--)
		{
			if (arr[j - 1] > arr[j])
			{
				swap(&arr[j - 1], &arr[j]);
			}
		}
	}
}

每一轮确认位置的元素情况如下

这里可以看出在第四轮的时候就已经有序了，但是还在循环挨个比对中，所以可以做出优化，设立一个中间变量标志flag=true，第二层如果发生交换就flag=false ，第二层循环运行完外面进行判断，如果flag没发生变化，那么就说明已经变得有序，直接退出循环不需要再循环下去

代码如下


void BubbleSort(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = true;
		for (int j = n-1; j>i; j--)
		{
			if (arr[j - 1] > arr[j])
			{
				swap(&arr[j - 1], &arr[j]);
				flag = false;
			}
		}
		if (flag)
			break;
	}
}

冒泡排序时间复杂度分析

首先第一重循环for (int i = 0; i < n; i++)，总共有n个元素，所以这一重循环要走n次，光这一层就要o（n）了

加上第二层循环for (int j = n-1; j>i; j--)

第一趟走n-1次，第三趟走n-2次，第四趟走n-3次………………2次，1次，0次

所以是个等差数列

1+2+3+…………+（n-3）+（n-2）+（n-1）

首项是1，末项是n-1，项数是n-1。

等差数列的求和公式是：
S = (首项 + 末项) × 项数 ÷ 2
在这个问题中，首项是1，末项是n-1，项数是n-1。

所以，我们可以将这些值代入求和公式中，得到：
S = (1 + (n-1)) × (n-1) ÷ 2

差不多就n^2/2 时间复杂度不考虑常数，所以冒泡排序是O（n^2）

二.直接插入排序

直接插入排序是将待排序的数组分为有序区和无序区两个部分，每次将一个无序区待排序的元素插入到前面已经排好序的有序区的过程，在这个过程中插入的元素要不断和有序区的元素进行比较调整，直到到达大小合适的有序位置。插完一个后，有序区的范围会扩大，相对的无序区的范围会逐渐减小，直到所有元素都在有序区，即已排好序。

一开始设定第一个元素单独是有序区的元素，因为单个元素天然有序

代码如下


void insertsort(int arr[],int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tamp = arr[end + 1];
		while (end >= 0)
		{
			if (tamp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tamp;
	}
}

代码解析

走一趟的代码可以简化成以下形式


int end = 0;
int tamp = arr[end + 1];
arr[end + 1] = arr[end];
arr[end + 1] = tamp;

这不就是一个用临时变量交换两个数组值的函数代码吗，如果这个数组只有两个元素，那么到这里就结束了。多个元素的话，外面肯定要套循环进行多个值比较。代码如下


for (int i = 0; i < n - 1; i++)
{
	int end = i;
	int tamp = arr[end + 1];
	if (tamp < arr[end])
	{
		arr[end + 1] = arr[end];
	}
	arr[end + 1] = tamp;
}

加了一层循环能保持数组所有的值都能参与比较，判断条件只能是n-1，不能是n。因为如果是n的话，那么end最大可以取n-1，可是arr[end]可是要和arr[end+1]进行比较的。如果判断条件是n，那么arr[end+1]就越界报错了。

此时这段代码依旧没有结束，因为此时这段代码只保证两两相比，但是我每次交换结束完一轮，只保证了我后面的大于我现在的值，也有可能我们交换之后前面依旧有数比我要大，这样就不满足排序。因此加入了第二层循环，来保证我要排序的数到达正确的位置


void insertsort(int arr[],int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tamp = arr[end + 1];
		while (end >= 0)
		{
			if (tamp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tamp;
	}
}

也可以写成以下的代码样子


void insertsort(int arr[],int n)
{
	for (int i = 1; i < n; i++)
	{
		int tamp = arr[i];
		int end = i - 1;
		while (end >= 0)
		{
			if (tamp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tamp;
	}
}

直接从1开始循环，end依旧是无序区和有序的分界线，好处是符合我们平时写循环的条件的样式，看起来顺眼多了

直接插入排序时间复杂度分析


void insertsort(int arr[],int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tamp = arr[end + 1];
		while (end >= 0)
		{
			if (tamp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tamp;
	}
}

第一重循环大概走n-1次，可以看做n次

假设待排序的数组基本就是有序的，那么就很少执行第二层循环里的交换和移动有序区的代码，所以可以近似成O（1），加上外层循环n次，所以有序的情况下，直接插入排序就是O（n）;

最坏的情况:倒序排成正序

因为end=i，而i最多取到n-2，所以要考虑从0一直到n-2的情况

end=0时，会移动1次，end=1时，会移动交换2次，end=2时，会移动交换3次…………end=n-2时会移动n-1次

因为第一层循环限制了，所以要把所有的次数加起来，所以是1+2+3+…………+（n-1）

这就是冒泡排序那里一样的等差数列，所以时间复杂度最坏是O（n^2）;

直接插入排序优化：折半插入排序

直接插入排序是一个一个地比较前面有序区的数值，直到找到合适的位置。由于有序区的数值是有序的，因此可以借助二分查找来直接定位位置，然后把这个位置后面的数值集体一次性移到后面

代码如下


void Bininsertsort(int arr[], int n) {  
    int i, j, low, high, mid;   
    for (i = 1; i < n; i++) { // 从索引1开始，因为索引0已经是排序好的  
        int tamp = arr[i]; // 取出当前要插入的元素  
        if (tamp < arr[i - 1]) { // 如果当前元素小于前一个元素，则进行二分查找  
            low = 0;  
            high = i - 1;  
              
            // 二分查找，找到插入位置  
            while (low <= high) {  
                mid = low + (high - low) / 2;  
                if (arr[mid] > tamp) {  
                    high = mid - 1;  
                } else {  
                    low = mid + 1;  
                }  
            }  
              
            // 将元素向后移动，为tamp腾出空间  
            for (j = i - 1; j > high; j--) {  
                arr[j + 1] = arr[j];  
            }  
              
            // 插入tamp到正确的位置  
            arr[high + 1] = tamp;  
        }  
    }  
}

折半插入排序和直接插入排序移动次数时间复杂度上来看并没有优化，只是变分散移动为集中移动。但是就折半插入减少了关键字的比较次数，就平均性能来讲折半查找优于顺序查找，所以折半插入排序还是优于直接插入排序。

折半插入排序虽然优化了查找，但是没有优化移动次数，只是直接插入排序是一个一个挪动交换，这是一堆一堆挪动。时间复杂度依旧是O（n^2）

三.简单选择排序

简单选择排序也是划分为有序区和无序区，不过不是一个一个从无序区取一个元素出来和有序区的挨个比对交换。而是每次都从无序区中找出最小的那个数和有序区的数进行交换。

代码如下


void selectsort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[min])
				min= j;
		}
		if (min != i)
			swap(&arr[min], &arr[i]);
	}

一开始也把第一个元素默认为有序的，比直接插入排序好的地方在于因为每次都是取最小的数出来，所以无序区待排序的数据，只需要和有序区最后一个元素进行比较就行了。第一轮来讲，因为和第一个元素进行比较，取出无序区的最小的元素进行比较交换，这样第一个最小的元素位置已经确认在第一个位置，往后所有的元素只会比这次还小,所以这个元素不用参与往后的排序比较了，有序区元素加1，有序区扩大。选择排序本质上就是在无序区找最小的，次小的，次次小的...........

简单选择排序优化：双向选择排序

上面的做法是每次从无序区选出最小的插到前面，其实也可以同时选出最大的插到后面，这样前后都是有序区，只有中间是无序区。


void selectsort(int arr[], int n)
{	
		int end = n - 1, begin = 0;
		while (begin < end)
		{
			int min = begin; int max = begin;
			for (int i = begin+1; i<=end; i++)
			{
 
				if (arr[i] <arr[min])
				{
					min = i;
				}
				if (arr[i] > arr[max])
					max = i;
			}
			if (begin == max)
			{
				max = min;
			}
			if (min != begin)
			{
				swap(&arr[min], &arr[begin]);
				begin++;
			}
			if (max != end)
			{
				swap(&arr[max], &arr[end]);
				end--;
		     }
		}
}

对于只选小的选择排序只有一个有序区，而且有序区是不断变大的，所以用个变量 i 就可以做到有序区不断变大了。而对于双向的选择排序，实际上是两个有序区不断地往中间回合，所以用begin和end去控制有序区

正常来讲做完循环找大小就可以直接交换位置了，为什么交换前还要做个判断if (begin == max)

这是因为如果begin和max相等，那么begin和min先进行交换，begin此时的数值已经发生改变了，变成最小的数了。而max要找的最大的数被换到min那边了，所以直接max=min；

上图所示begin和max在同一个下标位置，按代码所示应该begin和min下标所在位置117发生交换，可是再往下执行max和end交换的代码，此时max所在的位置已经变成117了，117换到end的位置上去明显是错误的。130才是应该换到end位置上的数，可是他在min和begin交换的代码里已经换到min位置上了，导致错误。所以加上限制条件，如果max等于begin，直接让max等于min就行了，此时min位置上才是max和end交换正确的数。

双向选择排序和折半插入排序差不多都没在时间复杂度上优化多少，甚至比单向的选择排序还要麻烦一点，如果考试的话还是首选上面的单项选择排序

选择排序时间复杂度


void selectsort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[min])
				min= j;
		}
		if (min != i)
			swap(&arr[min], &arr[i]);
	}

对于第一层循环for (int i = 0; i < n - 1; i++)来说，大概要走n-1次

第二层循环for (int j = i + 1; j < n; j++) 因为每次要找最小值，简单选择排序最坏的情况也是倒序，最小的在第n-1个位置上也就是最后一个

min=0时，往后找最小值要走n-1次。

min=1时，往后要找n-2次

min=2时，往后找n-3次

…………………………

min=n-2时往后走1次；

依旧是等差数列，所以是o（n^2）

但是最好情况也是O（n^2）,最好的情况下是他本来就是升序，而我现在要排升序，if语句里的赋值不会执行。但是二层循环依旧会执行n-（i+1）次，因为他是通过比对数组里待排序的所有值来找到最小值。

双向选择排序时间复杂度


void selectsort(int arr[], int n)
{	
		int end = n - 1, begin = 0;
		while (begin < end)
		{
			int min = begin; int max = begin;
			for (int i = begin+1; i<=end; i++)
			{
 
				if (arr[i] <arr[min])
				{
					min = i;
				}
				if (arr[i] > arr[max])
					max = i;
			}
			if (begin == max)
			{
				max = min;
			}
			if (min != begin)
			{
				swap(&arr[min], &arr[begin]);
				begin++;
			}
			if (max != end)
			{
				swap(&arr[max], &arr[end]);
				end--;
		     }
		}
}

在第一层循环中，需要进行n/2轮迭代，因为每一轮迭代同时找到最小值和最大值。

在第二层循环中，对于找最小值的部分，第一次需要比较n−1次，第二次比较n−2次，以此类推，最后一次只需要比较1次，符合等差数列的规律。

同理，对于找最大值的部分，也是符合等差数列的规律。

四.希尔排序

希尔排序和直接插入排序一样都是插入排序，区别在于希尔排序是按照一定的规则距离进行分组，然后每组之间进行比较大小交换，达到相对有序。先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。


void shellsort(int arr[], int n)
{
	int gap = n;
	while (gap >1)
	{
		gap = gap / 2;
		for (int i = 0; i < n-gap; i++)
		{
			int end = i;
			int tamp = arr[end + gap];
			while (end >=0)
			{
				if (tamp < arr[end])
				{
					arr[end + gap] = arr[end];
					end = end - gap;
				}
				else
				{
					break;
				}
				arr[end + gap] = tamp;
			}
		}
	}
}

gap等于1时，其实就变成了直接插入排序了，希尔排序其实可以看做是直接插入排序的一种优化

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

希尔排序时间复杂度分析

希尔排序时间复杂度分析是一个复杂的问题，一直没有定论，一般认为它的复杂度是O（n^1.3）

它的时间是所取增量gap序列的函数，到目前为止增量gap的选取无一定论，但是无论怎么取最后一个增量必须等于1，对上面的代码gap的取法来说，每次后的gap是前一个gap的1/2,经过t=log2（n-1）后gap=1。

希尔排序的速度通常认为比直接插入排序快，当d=1时，希尔排序的做法和直接插入排序基本一致，但是直接插入排序只有在初始数据为有序的时候所需时间才最少，其他情况基本为n^2。而希尔排序一趟分为gap组，每组n/gap个元素，该趟的排序时间约为gap*（n/gap）^2=n^2/d,少于n^2。在希尔排序开始时增量gap比较大，分组比较多，每组的元素数少，所以各组内交换排序较快，后来gap逐渐减小，分组数逐渐减少，而各组的元素数目也变多，但是由于上一趟已经粗略的排过序了，相比之前已经有序很多了，所以新的一趟排序变快了，越往后越有序也越快。

五.快速排序

hoare版本

快速排序是任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

基本操作就是取队头或者队尾元素为基准，然后可以看做前后各一个指针，后面的指针因为要保持待排序的数组的后半部分都大于基准值，所以遇到大于等于的就直接跳过，往前走，直到遇到小于基准值的元素。前面的指针因为要保持数组的前半部分都小于基准值，所以遇到小于等于基准值的就直接跳过，往后走，直到找到大于基准值的元素。此时前面指针底下的是大于基准值的，后面指针底下的是小于基准值的，他们两个直接相互交换位置。如果前后指针都相遇的，那么就代表已经进行了一系列交换，这个相遇点的位置前面的都比他小，后面的都比他大。然后直接把基准值和这个相遇点的值进行交换，这个位置就是基准值排完序应该在的位置。

再然后按同样的方法递归处理左右区间，值得注意的是中间的数值因为已经排好序了，所以递归处理时他不参与。

快排其实就是每次都寻找一个大概的位置，前面的都比他小，后面的都比他大

代码如下


void QuickSort(int arr[], int left, int right)
{
	if (left >= right)
		return;
	int x = left;
	int l = left; int r = right;
	while (l < r)
	{
		while (l < r && arr[r] >= arr[x])
			r--;
		while (l < r && arr[l] <= arr[x])
			l++;
		swap(&arr[l], &arr[r]);
	}
	swap(&arr[l], &arr[x]);
	QuickSort(arr, left, l - 1);
	QuickSort(arr, l+1,right);
}

6为单个元素，left==right，递归往回走，递归过程如下图

挖坑法快排

挖坑法，总体思路就是先将基准值那里挖一个坑（一般是第一个元素），然后右边先走找比基准值小的数，找到了就把这个数填到前面的坑里，然后原地再挖个坑。再然后左边开始找大，找到了大之后把这个数填到右边之前挖的坑里，然后原地挖坑。最后相遇的地方把基准值填进去

代码如下


void QuickSort(int arr[], int low, int high)
{
	if (low >= high)
		return;
 
	int key = arr[low];
	int l = low, r = high;
 
	while (l < r) {
		while (l < r && arr[r] >= key) {
			r--;
		}
		if (l < r) {
			arr[l] = arr[r];
			l++;
		}
 
		while (l < r && arr[l] <= key) {
			l++;
		}
		if (l < r) {
			arr[r] = arr[l];
			r--;
		}
	}
 
	arr[l] = key;
 
	QuickSort(arr, low, l - 1);
	QuickSort(arr, l + 1, high);
}

前后指针版快排

前后指针版是让两个指针l和r同时放在开头，如果r要大于等于要查找的基准值x，那么人就往后走。如果r小于基准值，那么l前进一步和r进行交换。要限定条件，r是快指针，所以r不能超过数组的长度，所以直接r<=high就可以了，因为每次递归查找的长度不一样，所以不能用传递过来的数组长度n作为循环限制条件

代码如下


void QuickSort(int arr[], int low, int high)
{
	if (low >= high)
		return;
	int key = low;
	int prev = low; int cur = low;
	while (cur <= high)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
			swap(&arr[cur], &arr[prev]);
		cur++;
	}
	swap(&arr[prev], &arr[key]);
	QuickSort(arr, low, prev - 1);
	QuickSort(arr, prev+ 1, high);
}

为什么是++prev!=cur呢，prev是前置++，此刻作为判断条件的是已经加过后的prev，如果++prev==cur；说明他们在同一位置，所以可以不用交换。

这种方法是一直保持prev和cur之间的数值都是比基准值要大的，如果找到了比基准值要小的就只换到前面去，然后缩小比基准值大的数值的区间，直到两个指针之间没有比基准值要大的值（两个指针相遇就代表没有比基准值大的数值了），那么此时这个相遇的位置就是基准值应该呆的位置。

快排非递归写法

hoare写法

非递归写法就是用栈来控制左右区间边界，然后其他的处理与递归写法类似


void quicksort(int arr[], int left, int right)
{
    stack<int> s;
    s.push(right);
    s.push(left);
    while (!s.empty())
    {
        int l = s.top(); s.pop();
        int r = s.top(); s.pop();
        right = r; left = l;//因为每次的边界值都会改变，而进栈要用到边界所以每次都更新
        int x = l;
        while (l < r)
        {
            while (l < r && arr[r] >= arr[x])
                r--;
            while (l < r && arr[l] <= arr[x])
                l++;
            if (l < r) {
                swap(&arr[l], &arr[r]);
            }
        }
        swap(&arr[l], &arr[x]);
        x = l;
        if (x + 1 <= right)
        {
            s.push(right);
            s.push(x + 1);
        }
        if (left <= x - 1)
        {
            s.push(x - 1);
            s.push(left);
        }
    }
}

if (x + 1 <= right)
{
s.push(right);
s.push(x + 1);
}
if (left <= x - 1)
{
s.push(x - 1);
s.push(left);
}

这两个选择分支其实对应着递归快排中的if (left >= right) return;

如果x+1大于right说明一个元素都没有了，所以不进栈处理，left大于x-1也是一样的

right = r; left = l;//因为每次的边界值都会改变，而进栈要用到边界所以每次都更新

为什么要加一行这个，边界值一直在改变，比如我数组下标为0到11，总共12个元素。然后处理了一圈后，l=r=6，两边分为0到5和7到11。然后来第二次处理，左半边区间后进栈的，所以它先出栈，所以先处理左区间。左区间右可以分为0到2和4到5，此时右区间进栈，right边界坐标应该是5才对，但是right没更新，还是之前的11，这样就出错了。所以要在l和r刚出栈时重新赋值给left以及right，这样就保证边界一直在更新

前后指针版写法


void quicksort(int arr[], int left, int right)
{
    stack<int>s;
    s.push(right);
    s.push(left);
    while (!s.empty())
    {
        left = s.top(); s.pop(); right = s.top(); s.pop();
        int prev = left; int x = left; int cur = left;
        while (cur <= right)
        {
            if (arr[cur] < arr[x] && arr[++prev] != arr[cur])
            {
                swap(&arr[cur], &arr[prev]);
            }
            cur++;
        }
        swap(&arr[prev], &arr[x]);
        if (prev + 1 <= right)
        {
            s.push(right);
            s.push(prev + 1);
        }
        if (left <= prev - 1)
        {
            s.push(prev - 1);
                s.push(left);
        }
    }
   
}

在第一个代码中，更新left和right的原因是因为在每一次切分过程中，l和r的值会不断变化，需要将当前的l和r值更新到left和right中，以便在下一轮迭代中使用正确的left和right值。

而在第二个代码中，通过prev来维护小于基准值的元素的位置，prev的值是递增的，不会像第一个代码中的l和r那样不断变化，因此不需要更新left和right。在第二个代码中，只需要在找到基准值的正确位置后，将prev更新到left和right的位置即可。

总的来说，两个代码实现了不同的快速排序算法思路，因此在更新left和right的时机和方式上会有所不同。

快排时间复杂度分析


void QuickSort(int arr[], int left, int right)
{
	if (left >= right)
		return;
	int x = left;
	int l = left; int r = right;
	while (l < r)
	{
		while (l < r && arr[r] >= arr[x])
			r--;
		while (l < r && arr[l] <= arr[x])
			l++;
		swap(&arr[l], &arr[r]);
	}
	swap(&arr[l], &arr[x]);
	QuickSort(arr, left, l - 1);
	QuickSort(arr, l+1,right);
}

快速排序最好的情况是每一次划分都将n个元素划分为两个长度差不多相同的子区间，均匀二分也就是说每次划分所取的基准都是中值元素，划分的结果是基准的左,右两个无序子区间的长度大致相等，这样递归树高度为logn，而每一层划分的时间为O（n），因为需要遍历n个元素来进行比较和交换，虽然代码中是两重循环，但是l与r运行加起来最多也才整个数组的长度n，所以此时时间复杂度为O（nlogn）

均匀二分如下图所示

最坏的情况，有序的时候，升序或者降序

这样一次只能确定一个元素的位置，要一直往下递归，直到最后一个，递树的高度是n（包括n），要划分n-1次。加上每一层划分的时间n，所以最坏情况是O（n^2）

六.堆排序

一个一维数组逻辑上可以看做是一个完全二叉树，而堆是满足一定条件的完全二叉树。完全二叉树父节点=(左孩子节点-1)/2=（右孩子节点-2）/2 ，一维数组的下标可以按这种规则构成完全二叉树

一维数组可以构成数的形式为

大堆根节点比所有分支节点都要大，而小堆的分支节点比所有的分支节点要小

完全二叉树的建堆方式有两种，从父节点开始向下调整建堆，从孩子节点开始向上调整建堆

向上调整

向上调整建堆是从孩子节点开始依次和自己的父节点开始比较，如果建小堆的话孩子节点比父节点小那么就要交换，调整完一次后要去比较自己父节点的父节点是否依旧比自己大，直到到达最上面的根节点

代码如下


void adjustup(int arr[], int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
			swap(&arr[child], &arr[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}

向下调整

向下调整建堆是从父节点开始依次和自己的孩子节点去比较，但是值得注意的是要和最小的孩子比，这样交换才有意义。交换完之后再和自己孩子的孩子进行比较，只到达到最底层

代码如下


void adjustdown(int arr[], int n,int parent)
{
	int child = 2 * parent+ 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] < arr[child])
			child++;
		if (arr[parent] > arr[child])
			swap(&arr[parent], &arr[child]);
		parent = child;
		child = 2 * parent + 1;
	}
}

大堆调整


void adjustdown(int arr[], int n,int parent)
{
	int child = 2 * parent+ 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
			child++;
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

if (child + 1 < n && arr[child + 1] < arr[child])
child++;

这个条件是判断左右孩子哪个比较小，我默认左孩子比较小，如果右孩子比较小那么直接++就行了，因为在数组里他们是相邻的关系，只需要++j就可以找到右孩子

需要注意的是堆里面不要求左右平级的子树根节点哪个大，哪个小，只要他们是自己子树里面最大的就行

具体堆排序

以下都用小堆的情况来讲解

对于小堆来说，最小的都在最上面根节点上，只需每次取最小的放在根节点然后想办法取出来就行了。一般方法是将小堆根节点和最后一个节点交换，因为数组最后一个节点好取出，每次数组长度减1就相当于取出来了。然后将刚刚交换过去的节点往下调整堆，取个次小的再次到根节点。但是这样处理之后最后数组里呈递减趋势，所以如果你要排升序的话要建大堆，这样处理过后的数组最后一位是最大的。

代码如下


void adjustdown(int arr[], int n,int parent)
{
	int child = 2 * parent+ 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
			child++;
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
 
void heapsort(int arr[], int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		adjustdown(arr, n, i);
	int size = n-1;
	while(size>0)
	{
		swap(&arr[0], &arr[size]);
		adjustdown(arr,size, 0);
		size--;
	}
	
}

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
adjustdown(arr, n, i);

建堆的循环，n-1是数组的最后一个元素（也是树的最后一个叶子节点），（n-1-1）/2是堆里面最后一个非叶子节点（也就是最后叶子节点的父节点）。parent=（child-1)/2

因为最后一层叶子节点是不需要往下调整的，他下面没有元素了，所以得从倒数第二层最后一个有孩子节点的节点开始往下调。因为没有孩子节点就没有向下调整的必要了。

倒数第二层最后一个有孩子节点的节点调整完了后，减减就会处理隔壁的节点，因为数组里各个节点的下标是连续的，所以可以通过节点减减来访问到上面所有的节点（i--），再然后通过向下调整来保持堆结构，直到所有的节点向下调整完

while(size>0)
   {
       swap(&arr[0], &arr[size]);
       adjustdown(arr,size, 0);
       size--;
   }

这个循环是处理建好堆后具体处理排序，升序要建大堆，保证第一个根节点是最大的。swap(&arr[0], &arr[size]);交换根节点和最后一个节点，堆里最后一个节点再数组里也是最后一个节点

adjustdown(arr,size, 0);因为此时最上面根节点已经通过上一步操作换为堆里最后一个元素了，此时是不满足大堆根节点比下面的子节点要大的规则的，所以要向下调整来重新构成堆

size--;此时数组里最后一个元素已经通过上面操作换为最大的了，已经确定排完序之后的位置了，所以不需要参与剩下的运算了，所以直接size--

堆排序时间复杂度分析

向上调整建堆时间复杂度

一颗完全二叉树高度与节点数关系为h=log（N+1），推导与快排的递归树类似

向上建堆是每次要往上调整的，所以第一层调整次数为0，因为它上面根本没有数值给他调整了

向下调整建堆时间复杂度分析

从上面的分析可以看出来，向下建堆时间复杂度O（n）优于向上建堆的O（nlogn）的，所以建堆时一般都是采用向下建堆的

堆排序复杂度分析


void heapsort(int arr[], int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		adjustdown(arr, n, i);
	int size = n-1;
	while(size>0)
	{
		swap(&arr[0], &arr[size]);
		adjustdown(arr,size, 0);
		size--;
	}
	
}

这个向下建堆的循环时间复杂度O（n）

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
adjustdown(arr, n, i);

int size = n-1;
   while(size>0)
   {
       swap(&arr[0], &arr[size]);
       adjustdown(arr,size, 0);
       size--;
   }

首先while循环会走n-1次，size=0不会继续运行，所以外层循环是O（n）

其次循环里面有个向下调整，虽然向下调整建堆的过程是O（n）的，但是这里却是O（nlogn）。因为建堆是实际上从倒数第二层一直往下调整的，最底下不用调整，所以时间复杂度是O（n）。而从根节点0开始向下调整和向上调整耗费是一样的，所以是O（nlog）

为什么这里向下调整也和向上调整次数一样，因为堆排序要把第一个元素和最后一个元素对换，最后一个元素此时在根节点，如果是最坏情况，这个元素要一直调到最底层才能找到自己的位置，也就是要调自己的高度次减1，高度从1开始所以减1，第h层就是h-1次。这时间复杂度算法就和向上调整没什么区别了，因为向上调整也是调整自己的高度次减1。对于向下建堆来说，它是从倒数第二层来开始调整的，相比之下少了最后一层不用调整，所以时间复杂度要优越很多

七.二路归并排序

递归版本

二路归并排序是将待排序的数组分割为两部分，然后再挨个从头开始比对，每次选出最小的一个数值出来放到新建立的数组里（我默认排升序，降序的话就取最大的）。最后所有的都处理完再复制回原数组里。值得注意的是二路归并排序虽然也要递归，但是与快排不同的是快排是先处理再递归，而二路归并排序是先递归到最后一个元素再来归并。

代码如下


void MergeSort(int arr[],int left,int right)
{
	if (left >= right)
		return;
	int* tamp = (int*)malloc(sizeof(int) * (right - left + 1));//开辟临时数组
	int mid = (left + right) / 2;
		MergeSort(arr,left,mid);
		MergeSort(arr,mid+1,right);
		int i = 0;
		int l = left; int r = mid + 1;
		while (l<=mid && r <= right)
		{
			if (arr[l] < arr[r])
				tamp[i++] = arr[l++];
			else
			{
				tamp[i++] = arr[r++];
			}//把两边数组里小的插到tamp数组前面
		}
		while (l <= mid)//左边还有数值没处理完
		{
			tamp[i++] = arr[l++];
		}
		while (r <=right)//右边还有数值没处理完
		{
			tamp[i++] = arr[r++];
		}
		for (int i = left, j = 0; i <= right; i++, j++)//把处理完的数值复制回原数组
		{
			arr[i]=tamp[j];
		}
		free(tamp);//释放临时数组的空间
}

递归分解如下

非递归写法

归并排序递归写法是将整个区间二分递归分层，最后按照规则两两归并，递归分层到只有一个元素的时候才会停止下来，最后慢慢回溯处理两个元素的情况，然后是四个元素的情况，依次往上推。所以非递归写法，可以用gap一个临时变量来控制区间的大小，又1一直到n,每次都扩大两倍


void merge(int arr[], int n) {
    if (n <= 1) return;
 
    int* temp = (int*)malloc(sizeof(int) * n);
    if (temp == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
 
    int gap = 1;
    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            int begin1 = i;
            int end1 = begin1 + gap - 1;
            if (end1 >= n) {
                end1= n - 1;
            }
            int begin2 = end1 + 1;
            int end2 = begin2 + gap - 1;
            if (end2 >= n) {
                end2 = n - 1;
            }
 
            int k = 0;
            int left = begin1;
            int right= begin2;
 
            
            while (left<=end1 &&right <= end2) {
                if (arr[left] <= arr[right]) {
                    temp[k++] = arr[left++];
                }
                else {
                    temp[k++] = arr[right++];
                }
            }
 
           
            while (left <= end1) {
                temp[k++] = arr[left++];
            }
 
           
            while (right <= end2) {
                temp[k++] = arr[right++];
            }
 
          
            for (int j = begin1,i=0; j <=end2; j++,i++) {
                arr[j] = temp[i];
            }
        }
        gap *= 2;
    }
 
    free(temp);
}

if (end1 >= n) {
end1= n - 1;
}

if (end2 >= n) {
end2 = n - 1; 这两个选择分支保证了不会越界访问

越界了不会去使用它

Gap: 1

	`begin1: 0, end1: 0, value: 125`
	`begin2: 1, end2: 1, value: 116`
	`[合并后] [116, 125, 132, 158, 36]`

	`begin1: 2, end1: 2, value: 132`
	`begin2: 3, end2: 3, value: 158`
	`[合并后] [116, 125, 132, 158, 36]`

	`begin1: 4, end1: 4, value: 36`
	`(只有一个元素，不进行合并)`

Gap: 2

	`begin1: 0, end1: 1, values: [116, 125]`
	`begin2: 2, end2: 3, values: [132, 158]`
	`[合并后] [116, 125, 132, 158, 36]`

	`begin1: 4, end1: 4, value: 36`
	`(只有一个元素，不进行合并)`

Gap: 4

	`begin1: 0, end1: 3, values: [116, 125, 132, 158]`
	`begin2: 4, end2: 4, value: 36`
	`[合并后] [36, 116, 125, 132, 158]`

二路归并时间复杂度分析

首先因为每次都是均匀二分，所以是递归树的高度次logn，也就是logn，其次每一层的数据处理归并都不会超过数组的长度n，所以内部是O（n），最后时间复杂度是O（nlogn）

它和快排相比最坏情况也是O（nlogn），因为快排最坏情况可能递归n层，而归并排序固定了logn层，因为每次都是二分的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/436216