数据结构实验（七）

排序

1. 归并排序和快速排序

   • “Sorting Algorithm.cpp”

     // Test9-1：排序算法 (Sorting Algorithm)
     // Sorting Algorithm: Quick Sort and Merge Sort
     
     #include <iostream>
     #include <iomanip>
     using namespace std;
     
     // 归并排序 (Merge Sort)
     void merge(int a[], int b[], int low, int mid, int high)
     {
     	// 将 a[low..mid) 和 a[mid..high) 合并到 b[0..high)
     	int i = low, j = mid;	// i记录a[low..mid)起始位置，j记录a[mid..high)起始位置
     	int k = low;			// k记录b[0..high)起始位置	
     	while (i < mid && j < high)
     	{
     		// a[]从小到大放入b[]中
     		if (a[i] < a[j])
     			b[k++] = a[i++];
     		else
     			b[k++] = a[j++];
     	}
     	while (i < mid)			// 若a[mid..high)全部放入b[]中，将a[low..mid)剩余元素全部放入b[]中
     		b[k++] = a[i++];
     	while (j < high)		// 若a[low..mid)全部放入b[]中，将a[mid..high)剩余元素全部放入b[]中
     		b[k++] = a[j++];
     }
     
     void mergeSort(int a[], int left, int right)
     {
     	// 合并排序主控函数
     	int n = right - left;			// 数组长度
     	int* b = new int[right];
     	for (int m = 1; m <= n; m *= 2)	// 2-路归并
     	{
     		for (int low = left; low < right; low += m * 2)
     		{
     			int mid = low + m;
     			if (mid > right)
     				mid = right;	// 前一段长度
     			int high = mid + m;
     			if (high > right)
     				high = right;	// 后一段长度
     			merge(a, b, low, mid, high);
     		}
     		memcpy(a + left, b + left, n * sizeof(int));
     	}
     	delete[]b;
     }
     
     // 快速排序 (Quick Sort)
     int partition(int a[], int left, int right)
     {
     	// 以 a[left] 为中枢，将 a[left..right) 划分为左中右三部分，返回枢轴位置
     	int pivotKey = a[left];		// 枢轴
     	right--;					// 使right为a数组最后一个元素的索引
     	while (left < right)
     	{
     		// 若right对应的元素小于枢轴则交换
     		while(left < right && a[right] >= pivotKey)
     			--right;			// 满足要求，移动right指针
     		a[left] = a[right];
     		// 若left对应的元素大于枢轴则交换
     		while (left < right && a[left] <= pivotKey)
     			++left;				// 满足要求，移动left指针
     		a[right] = a[left];
     	}
     	// 若left == right，则枢轴的最终位置确定
     	a[left] = pivotKey;
     	return left;
     }
     
     void quickSort(int a[], int left, int right)
     {
     	// 快速排序主控函数
     	if (right <= left)
     		return;
     	int p = partition(a, left, right);		// 确定枢轴的位置
     	quickSort(a, left, p);					// 对子数组a[left, p)快排
     	quickSort(a, p + 1, right);				// 对子数组a[p+1, right)快排
     }
     
     // 输出函数
     void show(int a[], int left, int right)
     {
     	for (; left < right; left++)
     		cout << a[left] << " ";
     }
     
     int main()
     {
     	// 测试归并排序
     	int a[] = { 43, 68, 45, 63, 47, 78, 49, 63, 59, 75 };
     	int n = sizeof(a) / sizeof(int);	// 数组a的长度
     	cout.setf(ios::right);
     	cout << "未排序的数据：" ;
     	show(a, 0, n);
     	mergeSort(a, 0, n);
     	cout << endl;
     	cout << setw(14) << "*归并排序*：";
     	show(a, 0, n);
     
     	// 测试快速排序
     	int b[] = { 43, 68, 45, 63, 47, 78, 49, 63, 59, 75 };
     	quickSort(b, 0, n);
     	cout << endl;
     	cout << setw(14) << "*快速排序*：";
     	show(b, 0, n);
     	cout << endl;
     
     	return 0;
     }
     

   • 运行截图：