各大排序算法

冒泡排序（稳定、n^2）

每次将最大的放到序列尾

/*
	冒泡排序（n^2）
*/
void BubbleSort(int* arr, int len) {
	for (int i = 0; i < len; ++i) {
		int MaxIndex = 0;
		bool Is_Seq = true;				// 判断序列是否已经顺序
		for (int j = 1; j < len - i; ++j) {
			if (arr[j] > arr[MaxIndex])  MaxIndex = j;
			else Is_Seq = false;
		}
		if (true == Is_Seq) return;		// 序列已顺序，提前退出
		// 最大值移到序列尾
		int tem = arr[len - i - 1];
		arr[len - i - 1] = arr[MaxIndex];
		arr[MaxIndex] = tem;
	}
}

选择排序 （不稳定、n^2）

每次将最小的放到序列头（相反的冒泡排序）

/*
	选择排序（n^2）   好像反向的冒泡
*/
void SelectionSort(int* arr, int len) {
	for (int i = 0; i < len; ++i) {
		int MinIndex = i;
		for (int j = i; j < len; ++j) {
			if (arr[j] < arr[MinIndex]) MinIndex = j;
		}
		// 交换
		int tem = arr[MinIndex];
		arr[MinIndex] = arr[i];
		arr[i] = tem;
	}
}

插入排序（稳定、n^2）

序列从头到尾将元素逐个插入前面已经排好的子序列中的合适位置。

/*
	插入排序（n^2）
*/
void InsertionSort(int* arr, int len) {
	for (int i = 0; i < len; ++i) {
		int j = i;
		int tem;
		while (j > 0) { 
			if (arr[j] < arr[j - 1]) { 
				tem = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tem;
			}
			--j;
		}
	}
}

希尔排序 （不稳定、n^2）

插入排序的升级版本，插入排序仅仅和相邻的元素逐个比较，可认为插入排序的步长为1，而希尔排序却是设置一个初始步长gap，每跨越gap距离的元素分为一小组，将多个小组排好序后，步长gap减半，重复操作，直到步长为1时，进行最后一次排序，此时相当于插入排序。

/*
	希尔排序（n^2）
*/
// 交换俩个数
void Swap(int* arr, int i, int j) {
	int tem = arr[i];
	arr[i] = arr[j];
	arr[j] = tem;
}
void ShellSort(int* arr, int len) {
	int gap = 0;
	while (gap < len / 3) gap = gap * 3 + 1;
	while (gap >= 1) {
		for (int i = gap; i < len; ++i) {
			for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
				Swap(arr, j, j - gap);
			}
		}
		gap >>= 1;
	}
}

归并排序 （稳定、nlog^n）

运用分治递归的思想，将序列划分为俩部分，再将各部分再次划分为为俩部分，直到各部分只有一个元素，分结束，开始治。按原来划分的方式，原路返回，将俩部分排序后合并成一部分。

合并俩部分小序列：

#define MAX_NUM 20
// 合并操作
void merge(int* arr, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;
	int* tem = new int[MAX_NUM];
	while (i <= mid && j <= right)
		tem[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	while (i <= mid)
		tem[k++] = arr[i++];
	while (j <= right)
		tem[k++] = arr[j++];
	for (i = left; i <= right; ++i) 
		arr[i] = tem[i];
	delete[] tem;
}
// 归并排序
void MergeSort(int* arr, int left, int right) { 
	if (left >= right) return;
	int mid = left + (right - left) / 2;
    // 向下递归将序列分组
	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
    // 递归返回合并分组的俩部分
	merge(arr, left, mid, right);
}

快速排序（不稳定、nlog^n）

将序列中挑选一个元素作为"基准（pivot）"，将序列中比基准小的元素全部放到基准的左边，将序列中比基准大的元素全部放到基准的右边。再将基准左右俩边的小序列（不包含基准）递归用同样的方式调整，直到划分的小序列只有一个元素。此时，序列便排好序。

例子代码以序列的最左边的元素作为基准。

/*
	快速排序
*/
void QuickSort(int* arr, int left,int right) {
	if (left > right) return;
	int pivot = arr[left];	// 序列最左边的元素作为基准
	int i = left;
	int j = right;
	while (i < j) {
		while (i < j&&arr[j] >= pivot) --j;	// 从右边找一个比基准小的元素
		arr[i] = arr[j];	// 交换
		while (i < j&&arr[i] <= pivot)  ++i;// 从左边找一个比基准大的元素
		arr[j] = arr[i];	// 交换
	}
	for (int i = 0; i < 11; ++i)
		cout << arr[i] << " ";
	cout << endl;
	arr[i] = pivot;
	for (int i = 0; i < 11; ++i)
		cout << arr[i] << " ";
	cout << endl;
	QuickSort(arr, left, i - 1);
	QuickSort(arr, i + 1, right);
}

堆排序 （不稳定、nlog^n）

利用了二叉堆（小顶堆、大顶堆）的性质进行排序。

开始时将序列初始化为二叉堆。

// 数组初始化为大顶堆
void InitMaxHeap(int* arr, int len) {
	int P, C;
	for (int i = 1; i < len; ++i) {
		C = i;
		P = (C - 1) / 2;
		while (C > 0) { 
			if (arr[P] > arr[C]) break;
			swap(arr, P, C);
			C = P;
			P = (C - 1) / 2;
		}
	}
}

以数组形式的大顶堆为例：

每一次进行排序时，将堆顶元素（数组首位元素）与数组末尾元素交互；再将堆当中未排序的元素重新调整成新的大顶堆；重复操作，直到所有元素排序完。

// 堆调整
void Heap_adjust(int* arr, int len) {
	int P = 0;
	int C = 2 * P + 1;
	while (C <= len) {
		if (C < len&&arr[C] < arr[C + 1]) C = C + 1;
		if (arr[C] < arr[P]) break;
		swap(arr, P, C);
		P = C;
		C = 2 * P + 1;
	}
}
// 堆排序
void HeapSort(int* arr, int len) {
	InitMaxHeap(arr,len);
	while (len >=1 ) {
		swap(arr, 0, len - 1);
		--len;
		Heap_adjust(arr, len - 1);
	}
	
}