做网站有什么好的推荐,网站建设内存,4399小游戏电脑版页面,网站建设 移动端文章目录 冒泡排序选择排序插入排序归并排序数组版本链表版本归并排序-内部缓存法 快速排序#xff08;重点讲解#xff09;堆排序#xff08;重点理解#xff09;计数排序基数排序桶排序希尔排序总结408考研各数据结构C/C代码#xff08;Continually updating#xff09… 文章目录 冒泡排序选择排序插入排序归并排序数组版本链表版本归并排序-内部缓存法 快速排序重点讲解堆排序重点理解计数排序基数排序桶排序希尔排序总结408考研各数据结构C/C代码Continually updating 冒泡排序
时间复杂度 On2 空间复杂度 O1 冒泡排序的思想是从第一个开始遍历然后每次都把比较大的数据 移动到后面去那么在第一次交换的时候最大的数据已经到最后去了 以此类推第二次冒泡的话倒数第二个就是倒数第二大的数据。
#include stdio.hvoid bubbleSort(int arr[], int n)
{if (arr NULL || n 2){return;}int flag 0;// 这是第几轮for (int i 0; i n; i){flag 0;// 这一层的for循环的意思就是当前轮需要包含的数据的个数// 因为每一次冒泡都会有一个最大的数据到末尾去// 所以需要不断的减少需要参与计算的数据量for (int j 0; j n - 1 - i; j){if (arr[j] arr[j 1]){// 使用异或交换arr[j] arr[j] ^ arr[j 1];arr[j 1] arr[j] ^ arr[j 1];arr[j] arr[j] ^ arr[j 1];flag 1;}}//如果此时已经没有数据更新那么说明已经有序直接跳出循环if (flag 0){break;}}
}int main()
{int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组:\n);for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);bubbleSort(arr, n);printf(排序后的数组:\n);for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);return 0;
}
选择排序
时间复杂度 On^2 空间复杂度 O1 思路是从第一个开始遍历然后每次都选择最小的哪一个放到前面去。 分区间 将数组分为两部分一部分是已排序的另一部分是未排序的。初始时整个数组都被视为未排序。 找最小值 在未排序的部分中查找最小的元素。通常这是通过遍历未排序部分的所有元素并不断更新一个临时最小值和其索引来实现。 交换位置 一旦找到最小元素将其与未排序部分的第一个元素交换位置使其成为已排序部分的一部分。 增加已排序部分的大小 将已排序部分的大小递增同时减少未排序部分的大小。 重复 重复步骤2到步骤4直到整个数组都被排序。未排序部分会不断减小而已排序部分会逐渐增加。 完成 当未排序部分为空时排序过程完成整个数组被排序。 上面是我早期写的笔记比较书面。口语的意思其实就是在开始排序之前先记录下一次要插入的最小的数据的位置一开始其实就是0然后记录下来这个起始位置p并且设定这个起始位置的值为暂定的min最小值然后从起始位置开始遍历整个数组找到最小的那个数据并且记录下来这个位置的索引并且更新我们暂定的min的值为这个遍历到的更小的值。 之后我们遍历完毕一次数组之后我们就得到了从起始位置到达数组末尾中的那个最小值的索引和最小值。 此时我们进行交换将这个最小值交换到我们一开始设定的其实位置p当然我们肯定不能直接就覆盖了这个起始位置的值还需要将我们一开始设定的起始位置的值覆盖掉这个我们后来找到的最小值的索引不然这个最小值就会一直参与计算了。
#include stdio.hvoid selectionSort(int arr[], int n) {for (int i 0; i n - 1; i) {int min arr[i]; // 初始化最小值为当前元素int p i; // 用于记录最小值的索引// 在未排序部分查找最小值for (int j i 1; j n; j) {if (min arr[j]) {min arr[j];p j;}}// 如果找到更小的值交换它们if (p ! i) {int temp arr[p];arr[p] arr[i];arr[i] temp;}}
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组:\n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);selectionSort(arr, n);printf(排序后的数组:\n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
插入排序
时间复杂度 On2) 空间复杂度 O1 插入排序的概念是每次选取一个索引从0开始。然后判断当前数据是不是比前面一个小 如果是那么就开始交换并且一直交换直到比前面的大或者前面没有数据了为止。 因此插入在高度有序的情况下时间复杂度On最差On2 插入排序一般性能都比冒泡和选择排序好 因为他会在数据有序的时候直接结束内循环。 这里比较重点的就是插入排序每次遍历的时候是向前遍历也就是每次都要确保当前元素是大于前面元素的如果不成立也就是arr[j]arr[j1]那么插入排序就会开始向前交换元素。直到不成立或者遇到索引0. 我甚至认为插入排序最简单因为他实际有效的代码就两行
#include stdio.hvoid insertSort(int arr[], int n) {//从第一个元素开始遍历然后内循环比较当前元素的前面一个元素和当前元素的关系for (int i 1; i n; i) {// 这里的条件判断就是 j 前面还有数据并且前面的 j 比后面的数据大// 那么就需要进行一次交换for (int j i - 1; j 0 arr[j] arr[j 1]; j--) {// 使用异或交换arr[j] arr[j] ^ arr[j 1];arr[j 1] arr[j] ^ arr[j 1];arr[j] arr[j] ^ arr[j 1];}}
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);printf(原始数组:\n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);insertSort(arr, n);printf(排序后的数组:\n);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
归并排序
数组版本
时间复杂度 Onlogn 空间复杂度 On 归并排序的思路 使用递归的方式不断将数组进行拆分拆分为左右两个等大小的数组。 由于递归的特性最后会拆分为长度最小为2的一个小区间之后我们就对这个小区间进行排序即可。 最后我们就可以得到多个的有序的小区间。 然后递归返回之后又会继续对这些小区间合并后的一个区间进行合并然后不断递归返回 就可以得到最终有序的一个区间了。 而递归调用的一个重要思路就是使用一个临时数组这个临时数组用于存放左右区间里的数据并且会按照大小进行排序。 思路为使用p1左指针使用p2右指针的方式左指针指向left右指针指向mid1 然后左右指针不断后移直到越界左指针边界为left—mid右指针边界为mid1—right。 然后将左右指针中指向的更小的数据拷贝到临时数组中此时临时数组中的元素在区间内有序。 之后将这个区间内有序的数据覆盖原有的数组即可。 之所以归并排序可以把时间复杂度缩短到nlogn是因为相对于时间复杂度n2的排序这些排序浪费了大量的比较功能 而归并排序每次都会比较两个范围的数据并且将其合并成一个区间内有序的数据然后再将这个区间去和更大的区间进行 一次排序那么这样子他的比较的操作就没有浪费而是保留了下来。 代码如下
#include stdio.h// 提前声明merge函数
void merge(int arr[], int left, int middle, int right);
void mergeSort(int arr[], int left, int right);void mergeSort(int arr[], int left, int right)
{if (left right){return;}//划分中轴int mid ((right - left) 1) left;//对左边进行归并mergeSort(arr, left, mid);//对右边进行归并mergeSort(arr, mid 1, right);//排序merge(arr, left, mid, right);
}
//对left到right这个区间上的数据进行排序
void merge(int arr[], int left, int mid, int right)
{// 创建一个辅助空间 left--right上有多少个数就开多大的空间int help[right - left 1];int i 0; // 提供给help使用的变量int p1 left; // 左侧数据的下标int p2 mid 1; // 指向mid1位置// 判断p1和p2是否越界如果都不越界// 那么谁小谁就拷贝到数组help中去while (p1 mid p2 right){help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}// 继续判断是否有没有拷贝完毕的数据// 可能是左半部分的p1没有拷贝完毕while (p1 mid){help[i] arr[p1];}// 也可能是右侧的p2没有拷贝完毕while (p2 right){help[i] arr[p2];}// 将help上面有序的数据拷贝到原数组上去就得到了区间上有序数据for (i 0; i (sizeof(help) / sizeof(help[0])); i){arr[left i] help[i];}
}int main()
{int arr[] {12, 11, 13,2312,123,556,887, 5, 6, 7};int arr_size sizeof(arr) / sizeof(arr[0]);printf(原始数组:\n);for (int i 0; i arr_size; i){printf(%d , arr[i]);}printf(\n);mergeSort(arr, 0, arr_size - 1);printf(排序后的数组:\n);for (int i 0; i arr_size; i){printf(%d , arr[i]);}printf(\n);return 0;
}
链表版本
相对于使用数组使用链表的归并排序的空间复杂度为O1。 时间复杂度不变。 链表方式的归并排序与数组方式的归并排序有一些不同因为链表不支持随机访问需要特别考虑如何拆分和合并链表。 大概的实现思路如下
分割链表 首先将原始链表拆分为两个子链表。可以使用快慢指针方法即使用两个指针一个慢指针每次前进1步另一个快指针每次前进2步找到链表的中点。然后将链表从中点分为两个子链表。重复这个过程直到链表不能再分割。
递归排序 对分割得到的两个子链表递归应用归并排序。这将重复分割和排序的过程直到每个子链表只包含一个元素或为空。这些子链表是已排序的。
合并有序链表 合并两个有序链表这是归并排序的核心操作。创建一个新的链表作为合并结果然后从两个子链表中逐个选择较小的节点并将其添加到新链表中直到两个子链表都为空。这将创建一个有序的合并链表。
返回结果 返回合并后的有序链表这就是排序完成的链表。
#include stdio.h
#include stdlib.hstruct ListNode {int val;struct ListNode* next;
};struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {if (!l1) return l2;if (!l2) return l1;struct ListNode dummy;struct ListNode* tail dummy;dummy.next NULL;while (l1 l2) {if (l1-val l2-val) {tail-next l1;l1 l1-next;} else {tail-next l2;l2 l2-next;}tail tail-next;}if (l1) tail-next l1;if (l2) tail-next l2;return dummy.next;
}struct ListNode* findMiddle(struct ListNode* head) {if (!head) return NULL;struct ListNode* slow head;struct ListNode* fast head;while (fast-next fast-next-next) {slow slow-next;fast fast-next-next;}return slow;
}struct ListNode* mergeSort(struct ListNode* head) {if (!head || !head-next) return head;struct ListNode* middle findMiddle(head);struct ListNode* secondHalf middle-next;middle-next NULL;struct ListNode* left mergeSort(head);struct ListNode* right mergeSort(secondHalf);return merge(left, right);
}void printList(struct ListNode* head) {struct ListNode* current head;while (current ! NULL) {printf(%d , current-val);current current-next;}printf(\n);
}void insert(struct ListNode** head, int val) {struct ListNode* newNode (struct ListNode*)malloc(sizeof(struct ListNode));newNode-val val;newNode-next *head;*head newNode;
}int main() {struct ListNode* head NULL;int n, val;printf(输入链表元素的数量: );scanf(%d, n);printf(请开始输入链表元素\n);for (int i 0; i n; i) {scanf(%d, val);insert(head, val);}printf(Original list:\n);printList(head);struct ListNode* sortedList mergeSort(head);printf(Sorted list:\n);printList(sortedList);return 0;
}
归并排序-内部缓存法
使用这个方法可以让归并排序的空间复杂度变为O1但是归并排序将会失去稳定性。 既然如此还不如直接用堆反正也是不稳定而且空间复杂度也为O1。 有兴趣的可以自己搜索一下
快速排序重点讲解
时间复杂度Onlogn 空间复杂度On 快速排序是我们最常用的排序算法也是性能比较好的一种时间算法。 因此我会重点讲解快速排序的实现思路。 在上面我们提到了归并排序其实现的思想是将对整个数组的操作通过递归的方式变为对一小块区间的排序操作也就是说合理的使用递归等过程是可以优化性能的。那么快排也可以。 可以思考如下一个场景假设有一个数组元素内容是1353467126。 假设我们有一个需求是通过给定一个数据然后要求我们的代码使得数组中的小于等于这个数据的元素出现在这个元素的左边而如果是大于这个数据的元素出现在数组的右边。 也就是相当于我们通过给定的这个数对数组进行了一个划分对于给出的数target恒有 数组左侧于target的数据小于target数组右侧于target的数据大于target。 那么很容易通过双指针的方式得到这样子的代码 //指定一个数据 然后比这个数据大的数据放在右边比这个数据小于等于的放在左边。void smallLeftBigRight(int arr[],int target){int slow 0;int fast 0;while (fastarr.length){if (arr[fast]target){arr[slow]^arr[fast];arr[fast]^arr[slow];arr[slow]^arr[fast];slow; }fast;}}输入一个数组之后我们就可以发现数组中某个位置左右的数据是小于和大于我们给出的数据的如下 可以发现经过我们简单的这样子的操作数据好像看起来有了那么一点顺序。 是的快排就是基于这样子的一个思想设定一个基准要求基准值左边的数据小于等于基准值基准值右边的数据大于基准值。并且通过递归的方式直到所有的区间符合要求。 那么如果我们要实现上面的说法应该如何实现呢 实现思路1 依旧是上面的数组我们选定最后的一个数据为基准设定为target然后要求小于等于这个数据的出现在这个数据的左边大于这个数据的出现在这个数据的右边。 然后我们通过遍历的方式从左到右遍历这个数组如果遇到的值小于target就继续后移因为合理如果遇到的值大于target我们就将这个值交换到数组的末尾去这样子大的值就放到后面了当然如果是这种情况由于我们不确定换过来的数据是否大于target我们的指针是不能增加的然后在进行一次上面的比较才确定是否增加。循环往复直到右边交换的值都已经比当前target大。 那么此时我们就按照上面的代码中得到了这样子一个部分有序的数据了然后此时我们将大于这个数据的第一个数据与这个最后一个数据进行交换交换后target的索引为index那么我们此时就得到了这个target数据左边的数据都小于这个数据右边的都大于这个数据。 然后我们继续缩短这个范围根据这个数据划分出来的左右边界继续执行这个流程左边的那一边从最左边的索引开始left然后右侧范围为index 而右边也重复这样子的过程其左边界为index1右边界为right。不断执行这样子的递归操作直到左指针和右指针碰撞我们就可以返回。 按照这样子的思路我们可以发现其时间复杂度最差为On2因为在数据高度有序的情况下例如12345。那么我们的过程其实每次都是这个数据自己和自己交换因为左边的都是比它小的。大概的一个流程如下 所以按照我们上面的意思快排的时间复杂度在这个基准值非常差劲的时候时间复杂度 On2。压根就不快所以我们需要解决基准值很偏的问题。 代码实现如下我这里设定最左边的数据为中轴。 /*** 下面是对代码的逐步解释* p* public static int[] quickSortX(int[] arr, int start, int end)这是快速排序的入口函数* 它接受一个整数数组 arr 以及排序范围的起始位置 start* 和结束位置 end 作为参数并返回排序后的整数数组。* p* int pivot arr[start];选择数组中的第一个元素作为中轴值pivot。* p* int left start; 和 int right end;定义两个指针left 从左向右移动right 从右向左移动* 用于在数组中找到需要交换的元素。* p* 下面的 while (left right) 循环是快速排序的核心部分它在数组中找到需要交换的元素* 以确保中轴值左边的元素都小于等于中轴值中轴值右边的元素都大于等于中轴值。这个循环包含以下几个部分* p* 第一个 while 循环从左边开始找到一个大于或等于中轴值的元素。* 第二个 while 循环从右边开始找到一个小于或等于中轴值的元素。* 如果找到的左边元素等于右边元素则继续将 left 向右移动以避免出现无限循环。* 否则交换左边元素和右边元素的值确保左边元素小于中轴值右边元素大于中轴值。* 之后代码检查是否有需要递归排序的左半部分和右半部分。如果左半部分的起始位置小于左指针的前一个位置* 递归调用 quickSortX 对左半部分进行排序。同样如果右半部分的结束位置大于右指针的后一个位置递归调用* quickSortX 对右半部分进行排序。* p* 最后函数返回排序后的数组 arr。** param arr* param start* param end* return*/int[] quickSortX(int arr[], int start, int end) {int pivot arr[start];int left start;int right end;//范围合法性while (left right) {//设定pivot中轴值左边的数据要求比pivot小while (left right arr[left] pivot) {left;}//设定pivot中轴值右边的数据要比pivot大while (left right arr[right] pivot) {right--;}//循环停止时 存在 arr[right]pivotarr[left]//如果等于 那么继续让left指针后移一位if (left right arr[left] arr[right]) {left;} else {//否则就是直接交换他们两个的值即可//此时存在 arr[left]pivotarr[right]//交换数据int temp arr[left];arr[left] arr[right];arr[right] temp;}}if (start left - 1) {arr quickSortX(arr, start, left - 1);}if (right 1 end) {arr quickSortX(arr, right 1, end);}return arr;}这个时候按照我们上面的思想我们肯定希望我们的中轴值没有那么偏僻所以我们考虑使用一个随机的方式生成我们中轴的位置。那么我们按照master方式可以得到最快的效率Onlogn。 所以我们就有了目前使用的快速排序思路如下 实现思路2 /*** void quickSort(int[] arr)这是公共的快速排序入口函数。* 它接受一个整数数组 arr 并检查是否需要排序。如果数组为空或只包含一个元素它就不执行排序。否则它调用* quickSortO2 来进行快速排序。* p* void quickSortO2(int[] arr, int left, int right)这个函数执行实际的快速排序算法。* 它接受数组 arr 以及排序的范围从 left 到* right。该函数使用了随机选择中轴值的方法然后调用 partition 函数来划分数组并递归地对左右两部分进行排序。* p* swap 函数用于交换数组中的两个元素。这个函数通过位运算进行交换是一种非常快速的方法。* p* int[] partition(int[] arr, int left, int right)这个函数用于处理 arr[left...right]* 上的数据将数组按照中轴值进行划分。它返回一个包含两个元素的整数数组* 表示等于中轴值的区域的左边界和右边界。这个函数采用双指针法其中 lessBound* 表示小于区的右边界moreBound 表示大于区的左边界。* p* 首先通过将 arr[right] 作为中轴值初始化 lessBound 和 moreBound。* 使用 left 指针从左到右遍历数组元素。* 如果当前元素小于中轴值将其与 lessBound 右边的元素交换并将 lessBound 和 left 向右移动。* 如果当前元素大于中轴值将其与 moreBound 左边的元素交换并将 moreBound 向左移动。* 如果当前元素等于中轴值只将 left 指针向右移动。* 最后将 arr[right] 与 moreBound 处的元素交换将数组划分为小于、等于和大于中轴值的三个部分。* 返回 lessBound 1 和 moreBound它们分别表示等于区的左边界和右边界。* p* 这里对于partition方法我的实现和思考思路如下* p* 初始化 lessBound 为 left - 1即 lessBound 初始为-1表示小于区的右边界。* p* 初始化 moreBound 为 right即 moreBound 初始为10表示大于区的左边界。* p* 使用 left 指针从左到右遍历数组元素。* p* 当 arr[left]当前元素小于 arr[right]中轴值时执行以下操作* 交换 arr[left] 和 arr[lessBound 1]然后增加 lessBound 和 left。* 这表示我们将小于区的右边界向右扩展一个位置并将当前元素放入小于区。* 当 arr[left] 大于 arr[right] 时执行以下操作* 交换 arr[left] 和 arr[moreBound - 1]然后减少 moreBound。* 这表示我们将大于区的左边界向左扩展一个位置并将当前元素放入大于区。* 当 arr[left] 等于 arr[right] 时只将 left 指针向右移动因为相等的元素将留在等于区。* 最终left 指针遍历整个数组将数组划分为三个部分小于区、等于区和大于区。* p* 为了完成划分将 arr[right]中轴值与 arr[moreBound]大于区的左边界进行交换。这将把中轴值放到正确的位置。* p* 返回一个包含两个元素的数组[lessBound 1, moreBound]。这个数组表示等于区的左边界和右边界。* p* 其中对于 arr[left] arr[right] 这种情况我并没有left,是因为* 当前元素 arr[left] 大于中轴值 arr[right] 时我们将它放入大于区即 arr[moreBound - 1] 处。* 这意味着 moreBound 表示大于区的左边界。* p* 通过减少 moreBound 的值我们将大于区的左边界向左移动同时保持 left 指针不变。* 这是因为当前元素 arr[left] 已经被放入大于区而在下一次迭代中我们需要继续检查新的 arr[left]* 是否大于中轴值以确保大于区包含所有大于中轴值的元素。* p* 所以left 指针只在当前元素小于中轴值时执行 操作表示将当前元素放入小于区而在当前元素大于中轴值时* 只需要更新大于区的左边界 moreBound而不需要改变 left 指针。** param arr*/public static void quickSort(int[] arr) {if (arr null || arr.length 2) {return;}quickSortO2(arr, 0, arr.length - 1);}public static void quickSortO2(int[] arr, int left, int right) {if (left right) {swap(arr, left (int) (Math.random() * (right - left 1)), right);int[] p partition(arr, left, right);quickSortO2(arr, left, p[0] - 1); // 区域quickSortO2(arr, p[1] 1, right); // 区域}}//当前方法用于处理arr[left...right]上面的数据//默认以arr[right]做划分//返回等于区域左边界、右边界所以返回一个长度为2的数组resres[0],res[1]public static int[] partition(int[] arr, int left, int right) {int lessBound left - 1;//小于区右边界int moreBound right; //大于区左边界while (left moreBound) {//left表示当前数据的位置 arr[right] --划分值if (arr[left] arr[right]) { //当前数据小于划分值swap(arr, lessBound, left);} else if (arr[left] arr[right]) {swap(arr, --moreBound, left);} else {left;}}swap(arr, moreBound, right);return new int[]{lessBound 1, moreBound};}public static void swap(int[] arr, int i, int j) {//特别注意 如果ij那么会导致数据被抹除if (i j) {return;}arr[i] ^ arr[j];arr[j] ^ arr[i];arr[i] ^ arr[j];}对于记忆的话还是选择可读性比较好的方法1吧追求性能的时候可以考虑使用方法2。
堆排序重点理解
堆排序的时间复杂度是稳定的Onlogn 空间复杂度为O1 堆排序的思想是基于完全二叉树的。 堆排序会使得数据满足大顶堆或者小顶堆的特性。大顶堆的意思就是非叶子节点的值大于叶子节点。小顶堆则相反。 因此对于一个堆其插入数据不符合堆的特性的时候是需要进行堆化的也就是会将这个数据进行排序移动到合理的位置使其满足大顶堆的特性。
堆排序的详细步骤如下 建立堆从数组的中间元素开始从右至左或者从下至上对每个元素执行下沉操作即将元素下沉到适当的位置以确保树的每个分支满足堆的性质。这将创建一个有效的最大堆或最小堆取决于排序需求。
排序堆建立完成后根节点包含堆中的最大或最小元素。将根节点与堆的最后一个元素交换然后缩小堆的范围即排除掉最大或最小元素。接着对根节点执行一次下沉操作以确保新的根节点仍然是堆中的最大或最小元素。重复这个步骤直到堆为空。
重复重复步骤2直到整个数组被排序。
大部分讲解堆的博客中都会明确告诉你堆排序是需要在数组的末尾不断缩短边界的把堆顶元素和数组末尾元素进行交换然后在进行一次堆化不断循环往复就可以得到一个有序的数组。 这就是堆排序的精髓。 当然当然堆其实最最最最重要的不是堆排序而是堆的结构合理利用堆的结构可以解答非常非常非常多的题目。 比如如下这题 考研408真题
#include stdio.h// 升序排序堆排序 --- 使用大顶堆
void adjustHeap(int arr[], int i, int length) {int temp arr[i]; // 将当前非叶子结点保存for (int k 2 * i 1; k length; k k * 2 1) {if (k 1 length arr[k] arr[k 1]) { // 判断左孩子大还是右孩子大k; // 如果右孩子大就获得右孩子的索引}if (arr[k] temp) { // 判断孩子大还是当前节点大arr[i] arr[k]; // 将更大的向上排i k; // 大的元素就跑到了非叶子结点的索引去然后让 i 去更小数据的索引} else {break;}}arr[i] temp; // 大的数据被移上去了但是其原有位置的数据还没有被修改
}// 降序排序堆排序 --- 使用小顶堆
void adjustHeapDesc(int arr[], int i, int length) {int temp arr[i]; // 将当前非叶子结点保存for (int k 2 * i 1; k length; k k * 2 1) {if (k 1 length arr[k] arr[k 1]) { // 判断左孩子大还是右孩子大k; // 如果右孩子小就获得右孩子的索引}if (arr[k] temp) { // 判断孩子小还是当前节点小arr[i] arr[k]; // 将更小的向上排i k; // 小的元素跑到了非叶子结点的索引然后让 i 去更大数据的索引} else {break;}}arr[i] temp; // 小的数据被移上去了但是其原有位置的数据还没有被修改
}void heapSort(int arr[], int length) {// 构建小顶堆for (int i length / 2 - 1; i 0; i--) {adjustHeapDesc(arr, i, length);}printf(初始构造小顶堆: );for (int i 0; i length; i) {printf(%d , arr[i]);}printf(\n);// 将堆顶元素与末尾元素进行交换将最小数据沉到末尾// 重新调整结构使其继续满足小顶堆性质for (int j length - 1; j 0; j--) {int temp arr[0];arr[0] arr[j];arr[j] temp;// 重新调整堆排除已排序部分使其继续满足小顶堆性质adjustHeapDesc(arr, 0, j);}printf(小顶堆排序后的数组降序排列: );for (int i 0; i length; i) {printf(%d , arr[i]);}printf(\n);
}int main() {int arr[] {4, 10, 3, 5, 1};int length sizeof(arr) / sizeof(arr[0]);printf(原始数组: );for (int i 0; i length; i) {printf(%d , arr[i]);}printf(\n);heapSort(arr, length);return 0;
}
计数排序
时间复杂度On 空间复杂度On。 这是一种典型的用空间换时间的排序算法但是在数据差值非常大的情况下非常不合理。 并且这种排序由于不是基于比较的所以他需要对代码进行定制。 比如你的数据是一个结构体比较不是整型类型比较那么很明显代码你就得修改了。 计数排序Counting Sort是一种非比较性的整数排序算法其核心思想是通过统计每个元素在待排序数组中出现的次数然后根据这些统计信息构建一个有序的结果数组。
计数排序的基本思想可以概括为以下几个步骤
确定范围找到待排序数组中的最大值max和最小值min以便确定计数数组的大小范围。通常范围大小为max - min 1。
创建计数数组创建一个大小为max - min 1的计数数组用于存储每个元素出现的次数。初始时计数数组中的所有元素都初始化为0。
计数遍历待排序数组对于每个元素将计数数组中对应元素的计数值加一。这样计数数组的值表示每个元素在待排序数组中出现的次数。
累加计数对计数数组进行累加操作。将每个计数值更新为前面所有计数值的累加和。这一步是为了确定每个元素在排序后的结果数组中的位置。
构建结果数组创建一个与待排序数组相同大小的结果数组。然后从待排序数组末尾开始遍历对于每个元素根据计数数组中的值找到其在结果数组中的位置将其放入结果数组中并将对应计数值减一以表示一个相同元素已经放入结果数组。
复制结果将排序后的结果数组复制回待排序数组完成排序过程。
计数排序的核心思想是依靠计数数组来统计元素的出现次数并利用这些统计信息构建有序结果。它不需要进行元素的比较操作因此具有线性时间复杂度通常用于整数排序尤其适用于范围较小的整数。然而计数排序的主要限制是需要额外的内存来存储计数数组因此在元素范围较大的情况下可能会导致内存浪费。
#include stdio.hvoid countingSort(int array[], int size) {// 找到数组中的最大值以确定计数数组的大小int max array[0];for (int i 1; i size; i) {if (array[i] max) {max array[i];}}// 创建计数数组并初始化为0int countArray[max 1];for (int i 0; i max; i) {countArray[i] 0;}// 计算每个元素出现的次数for (int i 0; i size; i) {countArray[array[i]];}// 根据计数数组构建排序后的结果数组int resultArray[size];int resultIndex 0;for (int i 0; i max; i) {while (countArray[i] 0) {resultArray[resultIndex] i;resultIndex;countArray[i]--;}}// 将排序后的结果复制回原数组for (int i 0; i size; i) {array[i] resultArray[i];}
}int main() {int arr[] {4, 2, 2, 8, 3, 3, 1};int size sizeof(arr) / sizeof(arr[0]);countingSort(arr, size);printf(排序后的数组);for (int i 0; i size; i) {printf(%d , arr[i]);}return 0;
}
基数排序
最好、平均和最坏情况下的时间复杂度都为 O(d * (n k))其中 d 是最大元素的位数或者说基数。 n 是元素的数量。 k 是基数通常是10对于十进制整数或256对于字节。 在最理想情况下基数排序的时间复杂度主要受限于最大元素的位数通常情况下是线性的。
基数排序的空间复杂度取决于存储桶和辅助数组的空间开销通常是 O(n k)。 n 是元素的数量。 k 是基数通常是10对于十进制整数或256对于字节。 基数排序Radix Sort是一种非比较性的整数排序算法其核心思想是根据数字的位数位上的值来对整数进行排序。基数排序通常从最低有效位最右边的位开始逐渐向高位排序直到最高有效位最左边的位。
基数排序的主要思想可以分为以下几个步骤
准备桶准备一个辅助数组或桶用于存储整数元素。通常这个辅助数组是一个包含10个桶的数组0到9每个桶对应一个数字的可能取值0到9。
从最低有效位到最高有效位基数排序通常从整数的最低有效位个位开始依次向高位排序。对于每个位上的值进行一轮排序。
分配元素在每一轮排序中遍历待排序数组根据元素的当前位上的值将元素分配到相应的桶中。例如如果当前轮是按个位排序那么元素根据个位上的值放入对应的桶。
收集元素在分配元素到桶之后将桶中的元素按照顺序从0到9收集回原始数组。
重复排序继续上述步骤按照下一位的值进行排序直到完成排序。通常需要进行足够的排序轮次以确保所有位都被考虑到。
完成排序完成所有的排序轮次后原始数组中的元素已经按照其位上的值从小到大排列排序完成。
基数排序的关键思想是分配和收集过程通过多轮的分配和收集逐渐完成整数的排序。每一轮排序都是稳定的因为它不会改变相同位上元素的相对顺序。基数排序适用于整数排序尤其适用于整数的位数相对较少的情况。
优点
基数排序是稳定的排序算法不会改变相等元素的相对顺序。 适用于整数排序特别是位数相对较少的整数。 不需要比较操作因此性能通常比比较排序算法更高。 缺点
需要额外的存储空间来存储桶因此内存消耗较大。 适用范围有限不适合处理浮点数和字符串等非整数数据。 对于位数较多的整数排序轮次可能较多导致性能下降。
#include stdio.h// 获取数组中的最大值
int getMax(int arr[], int n) {int max arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}}return max;
}// 基数排序的辅助函数对数组按照指定位数进行计数排序
void countSort(int arr[], int n, int exp) {int output[n];int count[10] {0}; // 0到9用于统计每个数字出现的次数for (int i 0; i n; i) {count[(arr[i] / exp) % 10];}for (int i 1; i 10; i) {count[i] count[i - 1];}for (int i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}for (int i 0; i n; i) {arr[i] output[i];}
}// 基数排序
void radixSort(int arr[], int n) {int max getMax(arr, n);for (int exp 1; max / exp 0; exp * 10) {countSort(arr, n, exp);}
}int main() {int n;printf(请输入数组的大小: );scanf(%d, n);int arr[n];printf(请输入 %d 个整数:\n, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}printf(原始数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);radixSort(arr, n);printf(排序后的数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
如下是我Java使用基数排序的时候的代码看起来会更好理解。
public static void radixSort(int[] arr) {// 找到数组中的最大值以确定最大元素的位数int max arr[0];int maxLength 0;for (int i 1; i arr.length; i) {if (arr[i] max) {max arr[i];}}maxLength (max ).length(); // 最大元素的位数// 创建桶数组用于存储排序中间结果int[][] bucket new int[10][arr.length]; // 每个桶最多能容纳数组大小个元素int[] bucketCount new int[10]; // 记录每个桶中的元素个数int digitOfElement 0;// 进行多轮排序每轮排序根据元素的位数for (int i 0, n 1; i maxLength; n * 10, i) {// 将元素按照当前位数的值放入对应桶中for (int j 0; j arr.length; j) {digitOfElement arr[j] / n % 10;bucket[digitOfElement][bucketCount[digitOfElement]] arr[j];bucketCount[digitOfElement];}int index 0;// 依次从桶中取出元素按照顺序重组数组for (int k 0; k bucketCount.length; k) {if (bucketCount[k] ! 0) {for (int l 0; l bucketCount[k]; l) {arr[index] bucket[k][l];}}bucketCount[k] 0;}}System.out.println(Arrays.toString(arr));}
桶排序
桶排序Bucket Sort是一种非比较性的排序算法它的核心思想是将待排序的元素分配到不同的桶容器中然后对每个桶中的元素进行排序最后按照顺序合并各个桶的内容从而得到有序的结果。
桶排序的步骤如下
确定桶的数量首先确定使用多少个桶通常桶的数量是根据待排序数据的范围来确定的。如果数据范围较大可以使用更多的桶。
分配元素遍历待排序的元素根据每个元素的值将其分配到对应的桶中。例如元素值范围在0到99之间可以将0到9分配到第一个桶10到19分配到第二个桶以此类推。
对每个桶进行排序对每个非空的桶进行排序可以使用任何合适的排序算法如插入排序或快速排序。
合并桶按照桶的顺序将每个桶中的元素合并这就得到了有序的结果。
桶排序适用于特定的数据分布情况例如当待排序数据近似均匀分布在一定范围内时桶排序表现良好。它是一种线性时间复杂度的排序算法具体的性能取决于桶的数量和每个桶中元素的排序算法。桶排序通常用于外部排序外部存储器排序例如对大量磁盘数据进行排序。
#include stdio.h// 定义桶的数量这里使用固定数量的桶也可以根据实际情况动态分配
#define BUCKET_COUNT 10// 桶排序函数
void bucketSort(int arr[], int n) {// 创建桶每个桶是一个数组int buckets[BUCKET_COUNT][n];// 每个桶的元素数量初始化为0int bucketSize[BUCKET_COUNT] {0};// 找到最大值和最小值以确定数据范围int max arr[0], min arr[0];for (int i 1; i n; i) {if (arr[i] max) {max arr[i];}if (arr[i] min) {min arr[i];}}// 计算桶的范围和尺寸double range (double)(max - min 1) / BUCKET_COUNT;// 将元素放入桶中for (int i 0; i n; i) {int bucketIndex (int)((arr[i] - min) / range);buckets[bucketIndex][bucketSize[bucketIndex]] arr[i];}// 对每个桶中的元素进行排序这里使用插入排序for (int i 0; i BUCKET_COUNT; i) {for (int j 1; j bucketSize[i]; j) {int key buckets[i][j];int k j - 1;while (k 0 buckets[i][k] key) {buckets[i][k 1] buckets[i][k];k--;}buckets[i][k 1] key;}}// 将排序后的元素从桶中提取到原数组int index 0;for (int i 0; i BUCKET_COUNT; i) {for (int j 0; j bucketSize[i]; j) {arr[index] buckets[i][j];}}
}int main() {int n;printf(请输入数组的大小: );scanf(%d, n);int arr[n];printf(请输入 %d 个整数:\n, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}printf(原始数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);bucketSort(arr, n);printf(排序后的数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
希尔排序
希尔排序Shell Sort是一种排序算法它是插入排序的改进版本旨在克服插入排序在大规模数据集上性能较差的问题。希尔排序是由计算机科学家Donald Shell于1959年提出的它基于以下思想
希尔排序的核心思想将数组划分成若干个小的子数组然后对这些子数组进行插入排序。这些子数组的长度逐渐缩小最终变成1也就是对整个数组进行一次插入排序。通过这种分阶段的排序方式希尔排序能够在初始阶段快速减小乱序数据的规模使得后续插入排序的工作更加高效。
希尔排序的基本步骤如下
选择一个增量序列通常是一系列递减的整数最开始的增量通常是数组长度的一半。
使用选定的增量将数组分割成多个子数组每个子数组包含元素的索引相差增量。
对每个子数组执行插入排序即将子数组中的元素按照插入排序的方式排序。
逐渐减小增量重复步骤2和步骤3直到增量减小至1。
最后一次排序时增量为1实际上就是对整个数组进行一次插入排序这时的数组已经接近有序。
希尔排序的性能优点在于它具有更好的性能预测特别是对于中等大小的数据集。它可以在较短的时间内完成大部分排序工作然后对于仅需少量交换的有序数据集插入排序非常高效。然而希尔排序的性能高度依赖于所选的增量序列不同的增量序列可能导致不同的性能表现。
#include stdio.hvoid shellSort(int arr[], int n) {int i, j, increment;// 初始增量为数组长度的一半increment n / 2;// 逐渐缩小增量直到增量为1while (increment 0) {for (i increment; i n; i) {int temp arr[i];// 对间隔increment的元素进行插入排序for (j i; j increment arr[j - increment] temp; j - increment) {arr[j] arr[j - increment];}arr[j] temp;}// 缩小增量increment (increment 1) / 2;}
}int main() {int n;printf(请输入数组的大小: );scanf(%d, n);int arr[n];printf(请输入 %d 个整数:\n, n);for (int i 0; i n; i) {scanf(%d, arr[i]);}printf(原始数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);shellSort(arr, n);printf(排序后的数组);for (int i 0; i n; i) {printf(%d , arr[i]);}printf(\n);return 0;
}
总结
不具备稳定性的排序 选择、快速、堆排序也就是选快堆。 具备稳定性的排序 冒泡、插入、归并、一切桶排序思想下的排序。 目前没有找到时间复杂度为Onlogn额外空间复杂度为O1的排序算法。
时间复杂度空间复杂度是否稳定选择On2O1×冒泡On2O1√插入On2O1√归并OnlognOn√快速OnlognOlogn×堆OnlognO1×
基于上面的表我们可以知道在具体场景中我们需要选择性的选择排序算法大部分时候我们会选择使用快排因为他确实大部分时候最快。但是如果考虑稳定性我们就会使用归并。而如果没有额外空间可以给你使用那么就考虑堆排序。
408考研各数据结构C/C代码Continually updating 408考研各数据结构C/C代码Continually updating 这个模块是我应一些朋友的需求希望我能开一个专栏专门提供考研408中各种常用的数据结构的代码并且希望我附上比较完整的注释以及提供用户输入功能okfine这个专栏会一直更新直到我认为没有新的数据结构可以讲解了。 目前我比较熟悉的数据结构如下 数组、链表、队列、栈、树、B/B树、红黑树、Hash、图。 所以我会先有空更新出如下几个数据结构的代码欢迎关注。 当然在我前两年的博客中对于链表、哈夫曼树等常用数据结构我都提供了比较完整的详细的实现以及思路讲解有兴趣可以去考古。
