数据结构（十）：排序（直接/折半插入排序、希尔排序、冒泡排序、快速排序）

目录

一、直接插入排序

二、折半插入排序

三、希尔排序

四、冒泡排序

五、快速排序

---

一、直接插入排序

●  直接插入排序的动画演示详见：Comparison Sorting Visualization

●  原理：

1. 初始的 L[1] 可视为一个已经排好序的子序列
2. 查找出 L[i] 在 L[1...i-1] 中的插入位置 k
3. 将 L[k...i-1] 中的所有元素依次后移一个位置
4. 将 L(i) 复制到 L(k)

●  图示：

 ●  代码：

（无哨兵）：元素存放的下标从0开始

//无哨兵
void InsertSort(ElemType A[],int n)
{
	int i, j, temp;
	for(i=1;i
	{
		if(A[i]-1])
		{
			temp = A[i];
			for(j=i-1;j>=0&&A[j]>temp;j--)
				A[j + 1] = A[j];  //所有大于temp的元素都向后移动
			A[j+1] = temp;  //复制到插入位置
		}
	}
}

（有哨兵）：元素存放的下标从1开始

//有哨兵
void InsertSort2(ElemType A[],int n)
{
	int i, j;
	for(i=2;i<=n;i++)  //依次将A[2]~A[n]插入前面已排序序列
	{
		if(A[i]-1])
		{
			A[0] = A[i];  //复制为哨兵，A[0]不存放元素
			for (j = i - 1; A[0] < A[j]; j--)
				A[j + 1] = A[j];  //向后移动
			A[j + 1] = A[0];  //复制到插入位置
		}
	}
}

二、折半插入排序

●  原理：

        直接插入排序中，在寻找插入位置 k 的过程中，由于子序列已经有序，我们可以不必从后往前依次比较，采用折半查找定位插入位置，可以节省部分查找的时间（之后依次向后移动的时间并不会改变）

        注：折半查找中，需要特殊注意的是，当 A[mid] = A[0] 时，为了保证算法的稳定性，应继续在 mid 所指位置的右边寻找插入位置。

●  代码：

（有哨兵）：元素存放的下标从1开始

//折半插入排序
void BinaryInsertSort(ElemType A[],int n)
{
	int i, j, low, mid, high;
	for(i=2;i<=n;i++)   //依次将A[2]~A[n]插入前面已排序序列
	{
		A[0] = A[i];  //哨兵
		low = 1; high = i - 1;  //设置折半查找的范围
		while(low<=high)
		{
			mid = (low + high) / 2;
			if (A[mid] > A[0])  high = mid - 1;
			else low = mid + 1;  //包含了A[mid]=A[0]的情况
		}
		for (j = i - 1; j >= high + 1; j--) //也可以写成j>=low (统一后移操作）
			A[j + 1] = A[j];
		A[high + 1] = A[0];
	}
}

三、希尔排序

●  希尔排序的动画演示详见：Comparison Sorting Visualization

●  原理：

1. 先取一个小于 n 的步长 d1，把表中的全部记录分成 d1 组，所有距离为 d1 的倍数的记录放在同一组，在各组内进行直接插入排序。
2. 取第二个步长 d2

●  图示：

●  代码：

（元素存放下标从1开始）

//希尔排序
void ShellSort(ElemType A[], int n)
{
	//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
	int i, j, dk;
	for (dk = n / 2; dk >= 1; dk = dk / 2) //步长变化
	{
		for (i = dk + 1; i <= n; i++)
			if (A[i] < A[i - dk]) //需将A[i]插入有序增量子表
			{
				A[0] = A[i]; //暂存在A[0]
				for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk)
					A[j + dk] = A[j]; //记录后移，寻找插入的位置
				A[j + dk] = A[0]; //插入
			}//if
	}
}

四、冒泡排序

●  冒泡排序的动画演示详见：Comparison Sorting Visualization

● 原理：

1. 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。
   我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置）。
2. 下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

● 图示：

●  代码：

void BubbleSort(ElemType A[],int n)
{
	for(int i=0;i-1;i++)
	{
		bool flag = false;//表示本趟冒泡是否发生交换的标志
		for(int j=n-1;j>i;j--)//一趟冒泡过程
		{
			if(A[j-1]>A[j])//若为逆序
			{
				//交换
				int temp = A[j - 1];
				A[j - 1] = A[j];
				A[j] = temp;
				flag = true;
			}
		}
		if(!flag)
			return;
	}
}

五、快速排序

●  快速排序的动画演示详见：Comparison Sorting Visualization

●  原理及图示：

●  代码：

int Partition(ElemType A[], int low, int high)
{
	ElemType pivot = A[low]; //将当前表中的第一个元素设为枢轴
	while (low < high)
	{
		while (low < high && A[high] >= pivot) --high;
		A[low] = A[high]; //将比枢轴小的元素移动到左端
		while (low < high && A[low] <= pivot) ++low;
		A[high] = A[low]; //将比枢轴大的元素移动到右端
	}
	A[low] = pivot; //枢轴元素存放到最终位置
	return low; //返回存放枢轴的最终位置
}
 
//快速排序
void QuickSort(ElemType A[], int low, int high)
{
	if (low < high) //递归跳出的条件
	{
		int pivot_pos = Partition(A, low, high); //划分
		QuickSort(A, low, pivot_pos - 1);
		QuickSort(A, pivot_pos + 1, high);
	}
}