数据结构实验报告-内排序

实验目的

熟悉直接插入算法、折半插入算法、冒泡法、简单选择法、快速排序内排序算法，利用排序算法实现一些其他问题的求解。

实验内容

输入一组无序数据，分别使用直接插入排序、折半插入算法、冒泡排序、简单选择排序的方法，将其从小到大重新排序并输出。

评分标准

（1）实现基本功能                 80分

（2）实现菜单功能                 90分

（3）实现排序过程打印           100分

实验步骤

#include <stdio.h>
#include <stdlib.h>
void print(int* arr, int length) {
	for (int i = 0; i < length; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void menu() {//菜单打印
	printf("*********************************\n");
	int arr0[10] = { 22,1,44,56,6,15,99,45,21,3 };
	printf("待排序数据");
	print(arr0, 10);
	printf("***********1.插入排序************\n");
	printf("***********2.折半查找排序********\n");
	printf("***********3.冒泡排序************\n");
	printf("***********4.选择排序************\n");
	printf("***********5.快速排序************\n");
	printf("***********0.exit***************\n");
	printf("********************************\n");
}

void insertSort(int* arr, int length) {//插入排序
	//外循环-从第二个元素开始,与前面的元素比较并找到合适的位置进行插入
	for (int i = 1; i < length; i++) {
		//内循环-将该元素与前面的元素挨个比较[0,i-1]
		for (int j = 0; j <= i - 1; j++) {
			if (arr[i] < arr[j]) {
				//插入到j的前面
				//挪动元素
				int temp = arr[i];//先将该元素储存起来

				for (int k = i - 1; k >= j; k--) {
					arr[k + 1] = arr[k];//将j-i之间的元素后移
				}
				arr[j] = temp;
			}
		}
		print(arr, length);
	}
}
void binSearchSort(int* arr, int length) {//折半查找排序
	if (arr[1] < arr[0]) {
		//交换
		int temp = arr[0];
		arr[0] = arr[1];
		arr[1] = temp;
	}

	for (int i = 2; i < length; i++) {
		int temp = arr[i];
		int start = 0;
		int end = i - 1;

		int mid = 0;
		while (start <= end) {
			int mid = (start + end) / 2;

			if (arr[i] < arr[mid]) {
				end = mid - 1;
			}
			else if (arr[i] > arr[mid]) {
				start = mid + 1;
			}
		}
		//找到插入位置
		for (int j = i - 1; j >= start; j--) {
			arr[j + 1] = arr[j];
		}
		arr[start] = temp;
		print(arr, length);
	}
}
void bubbleSort(int* arr, int length) {//冒泡排序
	for (int i = 0; i < length - 1; i++) {
		//因为每次找到一个极值,所以只需要执行length-1次
		for (int j = 0; j < length - i - 1; j++) {
			//因为每次都能找到一个,所以j<length-1-i
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		print(arr, length);
	}
}
void selectSort(int* arr, int length) {//选择排序
	for (int i = 0; i < length - 1; i++) {
		int k = i;
		for (int j = i + 1; j < length; j++) {
			if (arr[j] < arr[k]) {
				k = j;
			}
		}
		//交换
		int temp = arr[k];
		arr[k] = arr[i];
		arr[i] = temp;
		print(arr, length);
	}
}
int partition(int* arr, int i, int j) {
	int x = arr[i];
	while (i < j) {
		//从后往前
		while (i < j && x <= arr[j]) {
			j--;
		}
		if (i < j) {
			//此时找到了位于右边区域且值小于枢纽的数
		//将左边的空位填补
			arr[i] = arr[j];
			i++;
		}
		//此时从前往后
		while (i < j && x > arr[i]) {
			i++;
		}
		if (i < j) {
			//此时找到了位于左边区域且值小于枢纽的数
		//将右边的空位填补
			arr[j] = arr[i];
			j--;
		}
	}
	arr[i] = x;
	return i;
}
void quickSort(int* arr, int i, int j) {//快速排序
	if (i < j) {
		int index = partition(arr, i, j);
		//快排左子表
		quickSort(arr, i, index - 1);
		//快排右子表
		quickSort(arr, index + 1, j);
	}
}
void text() {
	menu();
	int i = 1;
	while (i) {
		printf("请选择:");
		scanf_s("%d", &i);
		switch (i) {
		case 1: {
			int arr1[10] = { 22,1,44,56,6,15,99,45,21,3 };
			insertSort(arr1, 10);
			break;
		}
		case 2: {
			int arr2[10] = { 22,1,44,56,6,15,99,45,21,3 };

			binSearchSort(arr2, 10);
			break;
		}
		case 3: {
			int arr3[10] = { 22,1,44,56,6,15,99,45,21,3 };

			bubbleSort(arr3, 10);
			break;
		}
		case 4: {
			int arr4[10] = { 22,1,44,56,6,15,99,45,21,3 };

			selectSort(arr4, 10);
			break;
		}
		case 5: {
			int arr5[10] = { 22,1,44,56,6,15,99,45,21,3 };

			quickSort(arr5, 0, 9);
			print(arr5, 10);
			break;
		}

		default: {
			break;
		}
		}
	}
}
int main() {
	text();
	return 0;
}

实验结果