一.插入排序

1.直接插入排序

• 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 时间复杂度：最坏情况O(n^2)，最好情况O(n)（当输入序列已排序时）。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：稳定。

 void InsertSort(int arr[], int arrlen)
{
	if(arrlen <= 1)
		return;
	
	for(int i = 1 ; i < arrlen; ++i)
	{
		int data = arr[i];
		int j = i - 1;
		for(; j >= 0; j--)
		{
			if(data >= arr[j])
				break;
		}
		
		if(j< i - 1)
		{
			for(int m = i; m > j + 1; --m)
			{
				arr[m] = arr[m - 1];
			}
			arr[j + 1] = data;
		}
	}
}

2.折半插入排序

• 原理：基于直接插入排序原理，只是插入比较时使用二分查找来确定插入位置。
• 时间复杂度：最坏情况O(n^2)，最好情况O(n)（当输入序列已排序时）。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：稳定。

void BinaryInsertSort(int arr[], int arrlen)
{
	if(arrlen <= 1)
		return;
	
	for(int i = 1; i < arrlen; ++i)
	{
		int data = arr[i];
		int begin = 0, end = i - 1, half = 0;
		
		while(end >= begin)
		{
			half = (begin + end) / 2;
			if(data >= arr[half]) //必须是>=,这样才能保证排序稳定。
			{
				begin = half + 1;
				half = half + 1;
			}
			else
			{
				end = half - 1;
			}
		}
		
		if(half < i )
		{
			for(int m = i; m > half; --m)
			{
				arr[m] = arr[m - 1];
			}
			arr[half] = data;
		}
	}
}

3.希尔排序

• 原理：是插入排序的一种更高效的改进版本，将待排序的数组元素按下标的一定增量分组，对每组使用直接插入排序算法排序。随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。这种分组排序的思想减少了元素之间的比较和移动次数，从而提高了排序效率。
• n个元素直接插入排序平均时间复杂度为o(n^2),那么分为d组，每组n/d个元素，时间复杂度为d*(n/d)^2=n^2/d。
• 分组时d越大优化越明显，初始值一般取数组的1/2。
• 时间复杂度：依赖于增量序列的选择，范围在O(n log2 n)到O(n2)之间，平均O(n^1.3)。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：不稳定。

void ShellSort(int arr[], int arrlen)
{
	if(arrlen <= 1)
		return;
	int d = arrlen / 2;
	
	for(; d > 0; --d)
	{
		for(int c = 0; c < d; ++c)
		{
			for(int i = c + d ; i < arrlen; i = i + d) //步长改成d，直接调用直接插入排序算法。
			{
				int data = arr[i];
				int j = i - d;
				for(; j >= 0; j = j - d)
				{
					if(data >= arr[j])
						break;
				}
				
				if(j< i - d)
				{
					for(int m = i; m > j + d; m = m -d)
					{
						arr[m] = arr[m - d];
					}
					arr[j + d] = data;
				}
			}
		}
	}
}

二.交换排序

1.冒泡排序

• 原理：通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
• 时间复杂度：最坏情况O(n^2)，最好情况O(n)（当输入序列已排序时）。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：稳定。

void BubbleSort(int arr[], int arrlen)
{
	bool bchange = false;
	for(int n = 0; n < arrlen - 1 ; ++n)
	{
		bchange = false;
		for(int i = 0; i < arrlen - 1 - n; ++i)
		{
			if(arr[i] > arr[i+1])
			{
				int tem = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = tem;
				bchange = true;
			}
		}
		if(bchange == false)
			break;
	}
}

2.快速排序

• 原理：是一种高效的排序算法，它使用了分而治之的策略。快速排序的基本思想是通过一次排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
• 时间复杂度：平均情况O(n log n)，最坏情况O(n^2)（当输入序列已排序或逆序时）。
• 空间复杂度：O(log n)（递归栈空间，最好情况），O(n)（最坏情况）。
• 稳定性：不稳定。

 void QuickSort(int arr[], int arrlen)
{
	if(arrlen < 1)
		return;
	int i = 0, j = arrlen - 1;
	int v = arr[0];
	while(i != j)
	{
		for(; j != i; --j)
		{
			if(arr[j] < v)
			{
				arr[i] = arr[j];
				break;
			}
		}
		
		for(; i != j; ++i)
		{
			if(arr[i] > v)
			{
				arr[j] = arr[i];
				break;
			}
		}
	}
	assert(i == j);
	arr[i] = v;
	
	QuickSort(arr, i);
	QuickSort(arr + i + 1, arrlen - i - 1);
}

三.选择排序

1.直接选择排序

• 原理：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 时间复杂度：O(n^2)。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：不稳定。

void SelectSort(int arr[], int arrlen)
{
	if(arrlen <= 1)
		return;
	
	int min, orgin, index;
	for(int i = 0; i < arrlen - 1; ++i)
	{
		min = arr[i];
		index = i;
		orgin = arr[i];
		for(int cn = i + 1; cn < arrlen; ++cn)
		{
			if(arr[cn] < min)
			{
				min = arr[cn];
				index = cn;
			}
		}
		arr[i] = arr[index];
		arr[index] = orgin;
	}
}

2.堆排序

• 原理：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
• 时间复杂度：O(n log n)。
• 空间复杂度：O(1)（原地排序）。
• 稳定性：不稳定。

//把数组arr从index元素开始，len个元素大堆化。
/*
 @param *arr,需要排序的数组
 @param index, 数组开始的元素
 @param len,需要构建大堆的元素个数
 */
void Heapify(int *arr, int index, int len)
{
	if(index >= len)
		return;
	
	//root:n, LChild:2n + 1, RChild:2n + 2。
	int maxindex = index, maxv = arr[index], lindex = 2 * index + 1, rindex = 2 * index + 2;
	
	int lv = maxv, rv = maxv;
	if(lindex < len)
		lv = arr[lindex];
	if(rindex < len)
		rv = arr[rindex];
	
	if(lv > maxv)
	{
		maxindex = lindex;
		maxv = lv;
	}
	if(rv > maxv)
	{
		maxindex = rindex;
		maxv = rv;
	}
	
	if(maxindex != index)//需要调整
	{
		swap(arr[index], arr[maxindex]);
		//递归的调整受影响的子堆。
		Heapify(arr, maxindex, len);
	}
	
}


//原理：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
//时间复杂度：O(n log n)。
//空间复杂度：O(1)（原地排序）。
//稳定性：不稳定。
/*
 @param arr[],需要排序的数组
 @param arrlen，待排序的数组长度
 */
void HeapSort(int arr[], int arrlen)
{
	if(arrlen <= 1)
		return;
	
	//n个结点的完全二叉树，最后一个非叶子结点的索引是 n/2 - 1
	int lastn = arrlen / 2 - 1;
	
	//从最后一个非叶子结点开始构建最大堆
	for(int n = lastn; n >= 0; --n)
	{
		Heapify(arr, n, arrlen);
	}

	for(int i = 0; i < arrlen - 1; ++i)
	{
		//把根节点最大元素和末尾元素交换
		swap(arr[0], arr[arrlen - 1 -i]);
		
		//交换后调整最大堆
		Heapify(arr, 0, arrlen - 1 - i);
	}
	
}

四.归并排序

• 原理：采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
• 时间复杂度：O(n log n)。
• 空间复杂度：O(n)（非原地排序，需要额外的存储空间）。
• 稳定性：稳定。

/*
 @param arr[],需要排序的数组
 @param len，待排序的数组长度
 @param start, 待排序数组起始索引
 */
void MergeSort(int arr[], int len, int start = 0)
{
	if(len<=1)
		return;
	int leftlen = len / 2;
	int rightlen = len - leftlen;
	
	MergeSort(arr, leftlen, start);
	MergeSort(arr,  rightlen, start + leftlen);
	
	int* temp = new int[len];
	int i = start, j = start + leftlen, index = 0;
	
	for(; i < start + leftlen;)
	{
		if(j == start + len)
		{
			temp[index++] = arr[i++];
			continue;
		}
		for(;j < start + len;)
		{
			if(arr[i] <= arr[j])
			{
				temp[index++] = arr[i];
				++i;
				break;
			}
			else
			{
				temp[index++] = arr[j];
				++j;
			}
		}

	}
	
	for(;j < start + len; ++j)
	{
		temp[index++] = arr[j];
	}
	assert(index == len);
	for(int i = 0; i < len; ++i)
	{
		arr[start + i] = temp[i];
	}
	
	delete [] temp;
}

测试用例

int main()
{
	std::random_device rd; // 用硬件生成种子  
	std::mt19937 gen(rd()); // 以随机设备作为种子的Mersenne Twister生成器  
	// 定义随机数的范围  
	std::uniform_int_distribution<> dis(1, 100); // 定义一个在1到100之间的均匀分布  
	vector<int> vec;
	int sum = 0, checksum = 0;
	for(int cn = 0 ; cn < 10000; ++cn) //1000次测试
	{
		for(int arrlen = 1; arrlen < 50; ++arrlen)
		{
			vec.clear();
			sum = 0;
			int* arr = new int[arrlen];
			
			for(int m = 0; m < arrlen; ++m)
			{
				arr[m] = dis(gen);   // 生成随机数  
				vec.push_back(arr[m]);
				sum += arr[m];
			}
			
			//QuickSort(arr, arrlen);
			//BubbleSort(arr, arrlen);
			//InsertSort(arr, arrlen);
			//BinaryInsertSort(arr, arrlen);
			//ShellSort(arr, arrlen);
			//SelectSort(arr, arrlen);
			//HeapSort(arr, arrlen);
			MergeSort(arr, arrlen);
			checksum = arr[0];
			for(int i = 0; i < arrlen - 1; ++i)
			{
				checksum += arr[i+1];
				if(arr[i] > arr[i + 1])
				{
					for_each(vec.begin(), vec.end(), [](int v){
						cout << " " << v;
					});
					delete [] arr;
					assert(false);
					cout << "error!" << endl;
					return 0;
				}
			}
			assert(checksum == sum);
			delete [] arr;
		}
		if(cn % 200 == 0)
			cout << "test " << cn << " cnt finish" << endl;
	}
	return 0;
}

众所周知如果递归层次过多，就会超出操作系统的栈大小，从而导致爆栈程序崩溃，以上排序算法有不少使用了递归，你能根据上篇文章改写成循环吗，或者有初学者需要，评论区留言我来改写。

#长文创作激励计划##排序算法##编程#