数据结构实验八：排序的应用

目录

一、实验目的

二、实验原理

1.直接插入排序

2.快速排序

三、实验内容

实验1

代码

截图?

实验2

代码

截图

?

---

一、实验目的

1、掌握排序的基本概念；

2．掌握并实现以下排序算法：直接插入排序、快速排序。

二、实验原理

1.直接插入排序

其基本思想是将一个待排序的元素插入到已经排好序的部分。

1. 从第二个元素开始，将当前元素插入到已经排好序的序列中。
2. 将当前元素依次与已排序序列中的元素比较，找到合适的位置插入。
3. 重复以上步骤，直到所有元素都有序。

void insertion_sort(int arr[], int num) {
	for (int i = 1; i < num; i++) {
		int start = 0;//已排序好的数组中待排序的元素最后所在的位置
		int end = i;//加上待排序的元素的数组的最后一个元素的位置
		int temp = arr[i];
		for (int j = i - 1; j >= 0; j--) {//从后往前找到已排序的数组中第一个比待排序元素小的位置
			if (arr[i] > arr[j]) {
				start = j+1;
				break;
			}
		}
		for (int i = end; i > start; i--) {//比待排序元素大的都后移
			arr[i] = arr[i - 1];
		}
		arr[start] = temp;
	}
	return;
}

2.快速排序

?其基本思想是选择一个基准元素，将数组划分为左右两个子数组，使得左边的元素都小于等于基准，右边的元素都大于等于基准，然后对左右子数组递归地应用快速排序。

1. 选择基准元素（Pivot）： 从数组中选择一个元素作为基准元素。通常选择数组中的最后一个元素。

2. 划分阶段： 将数组中小于等于基准的元素放在基准的左侧，将大于等于基准的元素放在基准的右侧。这个过程称为划分（Partitioning）。

   • 初始化两个指针，i 指向数组的起始位置，j 指向数组的结束位置。
   • 从左到右找到第一个大于基准的元素，从右到左找到第一个小于基准的元素，交换它们的位置。
   • 重复上述步骤，直到 i 大于等于 j。
   • 将基准元素与 i 所指位置的元素交换。

3. 递归排序： 对划分得到的两个子数组分别递归地应用快速排序。

   • 对左侧子数组递归调用快速排序：quick_sort(arr, low, pi - 1)
   • 对右侧子数组递归调用快速排序：quick_sort(arr, pi + 1, high)

4. 合并结果： 在递归的最后阶段，数组会变得有序。整个过程重复直到整个数组排序完成。

//交换两个元素
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

// 根据基准元素将数组划分为两个子数组，并返回基准元素的位置
int partition(int arr[], int low, int high) {
	int pivot = arr[high];
	int i = (low - 1);

	for (int j = low; j <= high - 1; j++) {
		if (arr[j] <= pivot) {
			i++;
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i + 1], &arr[high]);
	return i + 1;
}

// 快速排序函数
void quick_sort(int arr[], int low, int high) {
	if (low < high) {
		int pi = partition(arr, low, high);

		// 递归地对左右子数组进行排序
		quick_sort(arr, low, pi - 1);
		quick_sort(arr, pi + 1, high);
	}
}

三、实验内容

实验1

使用直接插入排序算法对序列{49,38,65,97,76,13,27,49}进行从小到大排序，并且输出每一趟排序的结果。

代码

#include<iostream>
using namespace std;

void insertion_sort(int arr[], int num) {
	for (int i = 1; i < num; i++) {
		int start = 0;//已排序好的数组中待排序的元素最后所在的位置
		int end = i;//加上待排序的元素的数组的最后一个元素的位置
		int temp = arr[i];
		for (int j = i - 1; j >= 0; j--) {//从后往前找到已排序的数组中第一个比待排序元素小的位置
			if (arr[i] > arr[j]) {
				start = j+1;
				break;
			}
		}
		for (int i = end; i > start; i--) {//比待排序元素大的都后移
			arr[i] = arr[i - 1];
		}
		arr[start] = temp;
		for (int i = 0; i < 8; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
	}
	return;
}
int main() {
	int arr1[8] = { 49,38,65,97,76,13,27,49 };
	cout << "直接插入排序结果为" << endl;
	insertion_sort(arr1, 8);
	return 0;
}

截图?

实验2

使用快速排序算法对序列{49,38,65,97,49,13,27,76}进行从小到大排序，并且输出每一趟排序的结果。?

代码

#include<iostream>
using namespace std;

#include<iostream>
using namespace std;

//交换两个元素
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

// 根据基准元素将数组划分为两个子数组，并返回基准元素的位置
int partition(int arr[], int low, int high) {
	int pivot = arr[high];
	int i = (low - 1);

	for (int j = low; j <= high - 1; j++) {
		if (arr[j] <= pivot) {
			i++;
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i + 1], &arr[high]);
	return i + 1;
}

// 快速排序函数
void quick_sort(int arr[], int low, int high) {
	if (low < high) {
		int pi = partition(arr, low, high);
		for (int i = 0; i < 8; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
		// 递归地对左右子数组进行排序
		quick_sort(arr, low, pi - 1);
		quick_sort(arr, pi + 1, high);
	}
}

int main() {
	int arr1[8] = { 49,38,65,97,76,13,27,49 };
	cout << "快速排序结果为" << endl;
	quick_sort(arr1,0, 7);
	return 0;
}

截图

?