| 【算法与数据结构】排序详解（C语言） | 您所在的位置：网站首页 › 对数组进行排序c语言 › 【算法与数据结构】排序详解（C语言） |
【算法与数据结构】排序详解（C语言）
|
目录 前言 插入排序 希尔排序 选择排序 堆排序 冒泡排序 快速排序 hoare版本 编辑 挖坑法 前后指针版本 优化 非递归实现 归并排序 非递归实现 复杂度分析 前言🎄在生活中我们必不可少的就是对一组数据进行排序，所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。在处理数据时，我们时常也要对数据进行排序，根据不同的情境使用不同的排序可以达到事半功倍的效果，因此掌握多种排序的算法十分重要，今天就一起来学习一下几个常见的排序方法吧。 插入排序🎄就像我们在打扑克时候的整牌，我们先固定开始一部分的牌，让他们处于有序的状态，之后再根据大小把后面的排插入的前面的牌里面。这也正是插入排序的基本原理。 🎄 因此，我们需要遍历数组，最开始有序的数列只有一个便默认为有序，之后遇到一个新的数就拿那个新的数跟前面的数比，找到这个数在这个数列里对应的位置插入后，这个数列再次变成了一个新的有序数列。 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //从第一个开始往后选择到i一定是有序的 { int end = i; int tmp = a[i + 1]; while (end >= 0) //向前插入 { if (a[end] > tmp) //升序的排法 { a[end + 1] = a[end]; //数据往后挪 end--; } else { break; //不再小于就找到了自己的位置，跳出循环 } } a[end + 1] = tmp; //将数据插入目标位置 } } 复制代码 希尔排序🎄希尔排序法又称缩小增量法，是由插入排序发展而来的，当数组里的元素足够大时，插入排序便不占优势，若我们在直接插入排序之前就先对数组进行预处理的话，就可以很大程度上提高性能与效率。 🎄基本思想是：先选定一个整数，把待排序文件中所有记录分成有限个组，所有距离相同的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 🎄基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。 🎄这里我进行了一点优化，一次循环会找最大最小的值并将其放在两侧，并对范围进行缩进，由此可以适当提升效率。 // 选择排序 void SelectSort(int* a, int n) { //双指针的思想 int begin = 0; int end = n - 1; while (begin < end) { int max = begin; //找区间内最大最小值 int min = end; for (int i = begin; i a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } swap(&a[begin], &a[min]); //小的放前面 swap(&a[end], &a[max]); //大的放后面 begin++; //缩进区间 end--; } } 复制代码 堆排序🎄之前在将堆的实现的时候就讲了堆排序，但堆排序的实现并不需要创建一个堆，只是使用了堆的思想。构建一个大堆之后，堆顶的数据就是数组的最大值，将其放在最后一位，之后再次构建大堆，则第二次堆顶的数据就是数组第二大的值，由此循环便完成排序。 void adjustdown(heaptype* a, int n, int root) //n是数组的大小 { int parent = root; //找到向下调整的初始值 int child = parent * 2 + 1; //往下找其左孩子 while (parent < n) { if (child + 1 < n && a[child] > a[child + 1]) //找孩子里最小的那个 { child++; } if (child < n && a[parent] > a[child]) //父结点大于子结点就交换 { 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--) //从最后一个结点对应的父结点开始建堆 { AdjustDwon(a, n, i); //先构建一个大堆 } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); //最大的放在最后面 AdjustDwon(a, end, 0); //再次向下调整 end--; //缩进 } } 复制代码 冒泡排序🎄冒泡排序可以说是我们接触最早的排序，就像冒泡一样一点一点把数往后推。 🎄这是最早的快速排序算法，基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 🎄说人话就是刚开始以数组里的一个值定义一个 key ，让左右两个指针向中间逼近，右边的指针找比 key 小的，左边的指针就找比 key 大的，二者交换，最后左右指针相遇的位置，就是 key 这个值在数组里面所占的位置。之后根据递归使得每个数都找到他对应的位置。 🎄更加简便的话可以这样写。 int PartSort3(int* a, int begin, int end) { if (begin > end) { return 0; } int cur = begin+1; int prev = begin; int key = begin; while (cur a[begin]) { return end; } else { return begin; } } } else { if (a[mid] > a[end]) { return mid; } else { if (a[begin] > a[end]) { return end; } else { return begin; } } } } int PartSort1(int* a, int left, int right) { if (left > right) //区间大小小于等于1结束递归 { return 0; } int l = left; int r = right; int ret = getmid(a, left, right); swap(&a[ret], &a[left]); int key = left; while (l < r) { while (l < r && a[r] >= a[key]) //右边找比key小的 { r--; } while (l < r && a[l] right) { return 0; } int l = left; int r = right; int ret = getmid(a, left, right); swap(&a[ret], &a[left]); int key = left; while (l < r) { while (l < r && a[r] >= a[key]) { r--; } while (l < r && a[l] = end) { return; } //分区间 int mid = (begin + end) / 2; //区间：[begin,mid] [mid+1,end] _Mergesort(a, begin, mid, tmp); _Mergesort(a, mid+1, end, tmp); //归并 int left1 = begin; int left2 = mid + 1; int right1 = mid; int right2 = end; int i = begin; while (left1 |
【本文地址】