2017网站开发兼职,普宁旅游网站设计方案,怎样做网站手机客户端,网站建设营销制作设计1、排序的概念 排序是指的是将一组数据#xff08;如数字、单词、记录等#xff09;按照某种特定的顺序#xff08;升序或降序#xff09;进行排列的过程。排序算法是实现排序的程序或方法#xff0c;它们在软件开发和数据处理中扮演着至关重要的角色。
排序算法可以根据…1、排序的概念 排序是指的是将一组数据如数字、单词、记录等按照某种特定的顺序升序或降序进行排列的过程。排序算法是实现排序的程序或方法它们在软件开发和数据处理中扮演着至关重要的角色。
排序算法可以根据不同的标准进行分类如 内部排序与外部排序内部排序是指数据全部加载到内存中进行排序而外部排序则涉及处理大量数据这些数据可能太大而无法一次性放入内存。 比较排序与非比较排序比较排序是基于比较操作来决定元素之间的相对顺序如快速排序、归并排序等。非比较排序不通过比较来确定元素的顺序如计数排序、基数排序等。 稳定性稳定的排序算法能够保持相等元素的原始顺序而非稳定排序算法可能会改变相等元素的顺序。 时间复杂度算法执行所需的时间与输入数据量的关系。常见的时间复杂度有O(n)、O(n log n)、O(n^2)等。 空间复杂度算法执行过程中需要的额外空间量。 在线排序与离线排序在线排序是指数据一个接一个地处理而离线排序则是在所有数据都可用的情况下进行。
2、常见的排序算法 接下来我们一一实现
直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tem a[end 1];while (end 0){if (tem a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tem;}
} 排序思想是认为第一个元素是有序的然后从第二个元素开始排序先把元素保存到tem中然后从后往前遍历数组找到比tem大的就向后挪一位遍历完后把tem放到下标为ennd1的位置上继续排下一个数 看一下动图演示: 直接插入排序的
时间复杂度O(N^2)
空间复杂度O(1)
稳定性稳定 希尔排序
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 2;for (int i 0; i n - gap; i){int end i;int tem a[end gap];while (end 0){if (tem a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tem;}}
} 希尔排序Shell Sort是插入排序的一种更高效的改进版本由Donald Shell于1959年提出。它是基于插入排序的一种分组比较排序算法也被称为“缩小增量排序”。希尔排序的核心思想是将原始数据集分割成若干个子序列进行插入排序这些子序列由原始数据集中的元素按照增量序列划分而来。随着增量序列的减小整个数据集逐渐被整合成一个有序的序列。
动图演示 选择增量序列增量序列的选择对希尔排序的性能有很大影响。常见的增量序列有希尔原始序列N/2N/4...1Hibbard增量序列1, 3, 7, ..., 2^k - 1Knuth序列1, 4, 13, ..., (3^k - 1)/2等。 分组按照当前增量将数组分为若干子序列。例如如果当前增量是5那么索引为0, 5, 10, ...的元素将分为一组索引为1, 6, 11, ...的元素将分为另一组以此类推。 对各组进行插入排序在每个子序列上应用插入排序算法使得每个子序列有序。 减小增量重复上述步骤随着增量的减小子序列的间隔逐渐减小最终当增量为1时整个数组将作为一个序列进行一次插入排序此时数组应该是基本有序的所以最后一步的插入排序会非常快。 完成排序当增量减小到1时整个数组将作为一个序列进行最后一次插入排序此时数组已经基本有序所以排序会很快完成。
时间复杂度希尔排序的时间复杂度依赖于增量序列的选择。最坏情况下的时间复杂度为O(n^2)但是对于中等大小的数组实际运行时间可能接近于O(n log^2 n)。最佳情况下如果增量序列选择得当时间复杂度可以达到O(n log n)。 有人算出希尔排序的时间复杂度接近于O(N^1.3)我们记住就行了。
空间复杂度O(1)
稳定性不稳定
选择排序
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;for (int i begin 1; i end; i){if (a[i] a[mini])mini i;if (a[i] a[maxi])maxi i;}swap(a[begin], a[mini]);if (maxi begin)maxi mini;swap(a[end], a[maxi]);begin;end--;}
} 选择排序Selection Sort是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。 上面是对选择排序的优化同时选取最大和最小的值进行比较然后放在队头和队尾 if语句是为了当前数组中最大的数在最小的位置上会发生重复交换如果加个if语句可以避免这种情况如果不理解的小伙伴可以把if语句去掉调试一下去发现问题肯定会理解的更加透彻
冒泡排序
代码展示
//冒泡排序
void bubblesort(int* a, int n)
{for (int i 0; i n - 1; i){for (int j 0; j n - 1 - i; j){if (a[j 1] a[j]){swap(a[j 1], a[j]);}}}
} 冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
冒泡排序的基本思想是通过相邻元素之间的比较和交换每一轮比较后最大的元素会“冒泡”到数列的最后位置。这个过程会重复进行直到整个数列有序。
时间复杂度O(N^2)
空间复杂度O(1)
稳定性稳定 堆排序
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}}
//堆排序 排升序
void heapsort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
} 堆排序使用了二叉树的思想用向下调整建堆如果我们建的是小堆然后交换堆顶和堆最后一个元素这样最小的元素就到了最后然后依次向下调整就形成了升序
快速排序 快速排序Quick Sort是一种高效的排序算法由C. A. R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分其中一部分的所有记录的关键字均比另一部分的关键字小然后分别对这两部分记录继续进行排序以达到整个序列有序的目的。快速排序的核心是分治法Divide and Conquer策略。
void QuickSortHoare(int* a, int left, int right)
{if (left right)return;int begin left, end right;int keyi left;while (left right){while (leftright a[right]a[keyi])right--;while (left right a[left] a[keyi])left;swap(a[left], a[right]);}swap(a[keyi], a[left]);keyi left;QuickSortHoare(a, begin, keyi - 1);QuickSortHoare(a, keyi1, end);
}
快速排序还有改进的双指针法
//快速排序 双指针版本
void QuickSortTowPorters(int* a, int left, int right)
{if (left right)return;int keyi left;int prev left;int cur left 1;while (cur right){if (a[cur] a[keyi] prev ! cur)swap(a[prev], a[cur]);cur;}swap(a[keyi], a[prev]);keyi prev;QuickSortTowPorters(a, left, keyi - 1);QuickSortTowPorters(a, keyi1, right);
} 这段代码是比较精简的请看动图演示 归并排序
//归并排序
void _mergeSort(int* a, int begin, int end, int* tem)
{if (begin end)return;int mid (begin end) / 2;_mergeSort(a, begin, mid, tem);_mergeSort(a, mid 1, end, tem);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tem[i] a[begin1];elsetem[i] a[begin2];}while (begin1 end1){tem[i] a[begin1];}while (begin2 end2){tem[i] a[begin2];}memcpy(a begin, tem begin, sizeof(int) * (end - begin 1));
}void MergeSort(int* a, int n)
{int* tem (int*)malloc(sizeof(int) * n);assert(tem);_mergeSort(a, 0, n - 1, tem);free(tem);tem NULL;
} 归并排序Merge Sort是一种分治算法其核心思想是将一个大问题分解成若干个较小的子问题来解决然后将子问题的解合并起来得到原问题的解。在排序领域归并排序通过不断地将数组分成两半对每一半进行排序然后将排序好的两半合并在一起从而达到整个数组有序的目的。
归并排序的步骤可以分为两个主要部分分裂Divide和合并Merge。 分裂Divide 将数组从中间分成两个相等或接近相等的子数组。对这两个子数组分别进行归并排序。这个过程会递归进行直到子数组的长度为1此时子数组自然是有序的。 合并Merge 将两个有序的子数组合并成一个更大的有序数组。合并过程中需要一个临时数组来存放合并后的有序数组。比较两个子数组的前端元素将较小的元素放入临时数组然后移动对应的指针。重复这个过程直到所有元素都被合并到临时数组中。将临时数组的内容复制回原数组或者直接使用临时数组作为结果。 以下是归并排序的非递归实现比较难理解
//归并排序 非递归实现
void MergeSortNonR(int* a, int n)
{int* tem (int*)malloc(sizeof(int) * n);assert(tem);int gap 1;while (gap n){for (int j 0; j n; j 2 * gap){//重点难点int begin1 j, end1 begin1 gap - 1;int begin2 begin1 gap, end2 begin2 gap - 1;//处理越界问题if (begin1 n || begin2 n)break;if (end2 n)end2 n - 1;int i j;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tem[i] a[begin1];elsetem[i] a[begin2];}while (begin1 end1){tem[i] a[begin1];}while (begin2 end2){tem[i] a[begin2];}memcpy(a j, tem j, sizeof(int) *(end2-j1));}}
} 可以看一下动图展示 归并排序的总时间复杂度是O(n log n)。这意味着归并排序在最好、最坏和平均情况下都有相同的时间复杂度即O(n log n)。这使得归并排序在处理大数据集时非常可靠和高效。 需要注意的是归并排序的空间复杂度也是O(n)因为它需要一个与输入数组大小相同的临时数组来存储合并的结果。在实际应用中归并排序的常数因子较大因此在小数组上的排序性能可能不如其他简单排序算法如插入排序。然而对于大型数据集归并排序的优势就非常明显了。 制作不易希望对你有帮助大家一起加油
