排序算法

排序方法分类

• 插入类：插入排序、希尔排序
• 交换类：冒泡排序、选择排序
• 选择类：简单选择排序、堆排序
• 归并类：归并排序
• 分配类：基数排序

插入排序

以升序排列为例，代码如下：

//需要传入的参数有：待排序数组a[]、数组长度size
void InsertSort(int a[], int size) {
    //从第二个元素开始遍历插入（只有一个元素时，其本身就是有序的，因此不用从第一个元素开始遍历）
	for (int i = 1; i < size; i++) {
		int temp = a[i], j;
        //把所有大于本次选取元素的元素向后移动一个位置
		for (j = i - 1; j >= 0 && temp < a[j]; j--)
			a[j + 1] = a[j];
        //上述循环结束之后，j+1就是本次选取元素应该插入的位置
		a[j + 1] = temp;
	}
}

递归实现代码如下：

void InsertSort_digui(int a[], int size) {
	//只有一个元素时，其本身就是有序的,直接return
    if (size == 1) return;
    //先将数组a[]前size-1个元素调整为有序
	InsertSort_digui(a, size - 1);
    //之后的操作与循环遍历实现的过程相同
	int temp = a[size - 1], j;
	for (j = size - 2; j >= 0 && temp < a[j]; j--) 
		a[j + 1] = a[j];
	a[j + 1] = temp;
}

冒泡排序

以升序排列为例，代码如下：

void BubbleSort(int a[], int size) {
	//添加布尔型变量flag，为false时表示数组还不是完全有序，需要继续进入循环排序
	bool flag = false;
	for (int i = 0; i < size - 1 && !flag; i++) {
		//每次进入循环，先把flag值修改为true
		flag = true;
		//从数组最末端元素开始向前比较
		for (int j = size - 1; j > i; j--)
		//将较小值交换至前面，若发生交换，将flag修改为false
			if (a[j] < a[j - 1]) {
				int temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
				flag = false;
			}
	}
}

递归实现代码如下：

//更确切的说这个应该叫做“沉石排序”，因为这里的思路是从末端开始向前完成排序
void BubbleSort_digui(int a[], int size) {
	bool flag = true;
	for (int j = 0; j < size - 1; j++)
			if (a[j] > a[j + 1]) {
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = false;
			}
	//若flag为true，说明整个数组已经是有序的了，直接return
	if (flag) return;
	BubbleSort_digui(a, size - 1);
}

快速排序

void QuickSort(int a[], int left, int right) {
	//left == right，说明此次需要排序的部分只有一个元素，其本身是有序的，直接return
	if (left == right) return;
	int flagNum = a[left], low = left, high = right;
	while (low < high) {
		while (low < high && a[high] >= flagNum) high--;
		a[low] = a[high];
		while (low < high && a[low] <= flagNum) low++;
		a[high] = a[low];
	}
	a[low] = flagNum;
	QuickSort(a, left, low - 1);
	QuickSort(a, low + 1, right);
}