浙江大学数据结构MOOC-课后习题-第九讲-排序1 排序

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

冒泡排序

void buble_Sort()
{	int A[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];bool flag = false;int temp;for (int j = N - 1; j > 0; j--){	flag = false;for (int i = 0; i < j; i++){if (A[i] > A[i + 1]){temp = A[i];A[i] = A[i + 1];A[i + 1] = temp;flag = true;}}if (flag == false) break;}for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}return;
}

插入排序

#include <iostream>
#define MAXSIZE 100000void insertion_Sort()
{	/* 初始化 */int A[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];/* 算法 */int i, j, temp;for (i = 1; i < N; i++){temp = A[i];	/* 摸牌 */for (j = i; j > 0 && A[j - 1] > temp; j--)A[j] = A[j - 1];A[j] = temp;}/* 打印 */for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}}int main()
{	insertion_Sort();return 0;
}

希尔排序

#include <iostream>#define MAXSIZE 100000void shell_Sort()
{	/* 初始化 */int A[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];/* 算法 *///Sedgewick序列int Sedgewick[] = { 929, 505, 209, 109, 41, 19, 5, 1, 0 };int i, j, Si, D, temp;/* 选取初始增量 */for (Si = 0; Sedgewick[Si] >= N; Si++);/* 开始排序 */for (D = Sedgewick[Si]; D > 0 ; D = Sedgewick[Si++])/* 增量变动 */{	/* 插入排序 */for (i = D; i < N; i++)/* 从第二堆中开始抽牌 */{temp = A[i];//for (j = i; j >= D && A[j - D] > temp; j -= D)for (j = i; j > D && A[j - D] > A[i]; j -= D){A[j] = A[j - D];}A[j] = temp;}}/* 打印 */for (i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}}int main()
{	shell_Sort();return 0;
}

堆排序

#include <iostream>
typedef int ElementType;
#define MAXSIZE 100000void swap(int A[], int i, int j)
{int temp = A[i];A[i] = A[j];A[j] = temp;
}
void PercDown(int A[], int p, int N)
{/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */int parent, child;int r = A[p]; /* 存放根节点的值 */for (parent = p; (parent * 2 + 1) < N; parent = child){child = parent * 2 + 1;if (child != N - 1 && A[child] < A[child + 1])child++;	/* child指向左右孩子中较大者 */if (r >= A[child]) break;	/* 找到恰当的位置 */else A[parent] = A[child];	}/* 找到恰当的值，或者遍历完节点了 */A[parent] = r;
}void heap_Sort()
{	/* 初始化 */int A[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];/* 算法 *///建立最大堆for(int i = N / 2; i >= 0; i--)PercDown(A, i, N);/* 删除最大堆堆顶 */for (int i = N - 1; i > 0; i--){swap(A, 0, i);PercDown(A, 0, i);}/* 打印 */for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}}int main()
{	heap_Sort();return 0;
}

归并排序

#include <cstdlib>
#include <iostream>
typedef int ElementType;
#define MAXSIZE 100000void Merge(int A[], int tempA[], int L, int R, int rightEnd)
{int leftEnd = R - 1;int length = rightEnd - L + 1;int i = L;while (L <= leftEnd && R <= rightEnd){if (A[L] < A[R])tempA[i++] = A[L++];elsetempA[i++] = A[R++];}while(L <= leftEnd)tempA[i++] = A[L++];while(R <= rightEnd)tempA[i++] = A[R++];
}void Merge_pass(int A[], int tempA[], int N, int length)
{	int i = 0;for (i = 0; i <= N - 2 * length; i += 2 * length)Merge(A, tempA, i, i + length, i + 2 * length - 1);if (i + length < N)Merge(A, tempA, i, i + length, N - 1);else{for (; i < N; i++)tempA[i] = A[i];}
}void Mergy_Sort()
{	/* 初始化 */int A[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];/* 算法 */int* tempA = (int*)malloc(N * sizeof(int));int length = 1;if (tempA != NULL){while (length < N){Merge_pass(A, tempA, N, length);length *= 2;Merge_pass(tempA, A, N, length);length *= 2;}free(tempA);}else std::cout << "ERROR";/* 打印 */for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}}int main()
{	Mergy_Sort();return 0;
}