杭州微网站开发公司,模型网站大全免费,企业查询网,网页设计与制作教程重要吗【本节目标】 1. 排序的概念及其运用 2. 常见排序算法的实现 3. 排序算法复杂度及稳定性分析 1.排序的概念及其运用
1.1排序的概念 排序 #xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来… 【本节目标】 1. 排序的概念及其运用 2. 常见排序算法的实现 3. 排序算法复杂度及稳定性分析 1.排序的概念及其运用
1.1排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的 1.2排序运用 1.3 常见的排序算法 // 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
、void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)
// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int)*N);int* a2 (int*)malloc(sizeof(int)*N);int* a3 (int*)malloc(sizeof(int)*N);int* a4 (int*)malloc(sizeof(int)*N);int* a5 (int*)malloc(sizeof(int)*N);int* a6 (int*)malloc(sizeof(int)*N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];
}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();QuickSort(a5, 0, N-1);int end5 clock();int begin6 clock();MergeSort(a6, N);int end6 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
} 排序OJ(可使用各种排序跑这个OJ)912. 排序数组 - 力扣LeetCode 2.常见排序算法的实现
2.1 插入排序
2.1.1基本思想
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 2.1.2直接插入排序 当插入第 i(i1) 个元素时前面的 array[0],array[1],…,array[i-1] 已经排好序此时用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较找到插入位置即将 array[i] 插入原来位置上的元素顺序后移 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(N) 它是一种稳定的排序算法 4. 稳定性稳定 代码实现
void InsertSort(int* arr, int length)
{for (int i 0; i length-1; i){int endi;int temp arr[end 1];while (end 0){if (temp arr[end]){arr[end1] arr[end];}else{break;}end--;}arr[end 1] temp;}}
2.1.3希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达gap1时所有记录在统一组内排好序 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 时间复杂度可以即一个结论大概是N^1.3 代码实现 void SellSort(int* arr, int length)
{int gap length;while (gap1){gap gap / 3 1;for (int i 0; i length-gap; i){int end i;int temp arr[end gap];while (end0){if (temp arr[end]){arr[end gap] arr[end];end end - gap;}else{break;}}arr[end gap] temp;}}
}2.2冒泡排序
基本思路 左边大于右边交换一趟排下来最大的在右边 冒泡排序的特点包括 1. 冒泡排序适合处理元素集合越接近有序的情况时间效率会更高。 2. 冒泡排序的时间复杂度为O(N^2)性能较差不适用于处理大规模数据的排序。 3. 冒泡排序是一种稳定的排序算法相同元素的相对位置不会发生改变。 4. 冒泡排序的空间复杂度为O(N)是一种原地排序算法。 5. 冒泡排序是一种交换排序算法通过不断比较相邻的元素并交换位置来达到排序的目的。
代码实现
void BubbleSort(int* arr, int length)
{for (int i 0; i length-1; i){int flag 0;for (int j 0; j length-i-1; j){if (arr[j] arr[j 1]) {Swap(arr[j], arr[j 1]);flag 1;}}if (flag 0){break;}}
}
2.3堆排序
堆排序是一种基于二叉堆数据结构的排序算法其基本思路如下 构建最大堆或最小堆将待排序的数组视作一个完全二叉树并且通过调整父节点与子节点的关系使得每个父节点的值都大于或小于其子节点的值即构建最大堆或最小堆。 将堆顶元素与最后一个元素交换将根节点最大值或最小值与最后一个元素交换位置。 调整堆结构交换元素后调整堆结构使其重新满足最大堆或最小堆的性质。 重复步骤2和3重复进行上述步骤直到所有元素都被交换到对应的位置即完成排序。
堆排序的时间复杂度为O(nlogn)其中n为待排序数组的长度。堆排序是一种原地排序算法不需要额外的空间但性能较差且不稳定。 代码实现
void AdjustDown(int* arr,int length, int parent)
{int child parent * 2 1;while (childlength){if (child1length arr[child 1] arr[child]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child child * 2 1;}else{break; }}
}
void HeapSort(int* arr, int length)
{for (int i (length-1-1)/2; i 0; i--){AdjustDown(arr, length, i);}int end length - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}
