数据结构 |
您所在的位置:网站首页 › 交换排序和选择排序的关系是什么 › 数据结构 |
目录 排序的概念 排序的分类 插入排序 选择排序 交换排序 归并排序 排序的概念排序就是一系列数据,按照某个关键字(例如:销量,价格),进行递增或者递减的顺序排列起来. 排序的分类把待排序的数据插入到已经排好序的数据中,直到所有的数据插入完成,即就是直接插入排序。(如流行于陕西一带的纸牌游戏,挖坑)一般待排序的区间是第二个数到最后一个数。例如下面的例子就是待排序区间从 7 到 8。把第一个数当作已经排序的数据 希尔排序实在前面直接插入排序的基础上进行改进的一种排序。直接插入排序的变量 i 其实就是一个间隔,而希尔排序的间隔不是 1,它的间隔逐渐缩小直到为 1 的一种排序,因此又叫缩小增量法。它是对直接插入排序算法的优化,当间隔不为 1 的时候,都是预排序。第一次的间隔是 数据长度的三分之一再加一。即 gap = size / 3 + 1 选择排序就是在待排序的数据中选择一个最大的或者最小的放在带待排序数据的末尾。也可以是已经排好序的数据的开头。 //C语言 //选择排序 void Choice_Sort2(int arr[], int size) { for (int i = 1; i < size; ++i)//从下标为1 开始,找size - 1次 { int max = 0;//假设最大的数的下标是第 0 个 for (int j = 1; j arr[max]) { max = j;//如果找到比下标为max的元素还大的元素则把max的值进行改变 } } int temp = arr[size - i]; arr[size - i] = arr[max]; arr[max] = temp; } }堆排序就要用到前面学到的数据结构二叉树的知识了。堆的作用是什么呢?就是寻找最值。所以根节点肯定最大(大堆)或者最小(小堆)。我们把根节点和最后一个结点进行交换,数组最后一个数肯定就是最大或者最小的。最后又在剩下的数据里面建堆。 要注意的是升序建大堆,降序建小堆,下面复习一下堆的知识。 //C语言 //向下调整 void Adjust_down(int arr[], int size, int root) { while (1) { int left = root * 2 + 1; int right = root * 2 + 2; int min = left;//最小的为最左孩子 if (left >= size)//没有孩子结点 { return; } if (right < size && arr[right] < arr[left])//有右孩子 { min = right; } if (arr[root] = 0) { Adjust_down(arr, size, notlevel); --notlevel; } } void HeapSort(int arr[], int size) { //建堆 CreateBigHeap(arr, size); for (int temp = 1; temp < size; ++temp) { int t = arr[0]; arr[0] = arr[size - temp]; //这个值就是最后一个叶子结点。 arr[size - temp] = t; Adjust_down(arr, size-temp,0);//从根节点开始调整 } } 交换排序 冒泡排序冒泡排序是我们最熟悉的一种排序了吧,它的过程就是从第一个数开始,和第二个数比较,满足条件就进行交换,然后第二个数和第三个数进行比较满足进行交换,直到最后一个数,这是一个“泡”已经冒出。现在有从开始比较,这个时候总的比较的数减少一个,因为“泡”已经冒出了。冒泡排序一共会进行 size - 1次冒泡,每次的比较次数为size - i,i是比较的第几次。 //C语言 void Bubble_Sort(int arr[], int size) { assert(arr); for(int row = 0; row < size - 1; ++row) { int flag = 1; for(int col = 0; col < size - row - 1; ++col)//col是从0开始的 { if (arr[col] < arr[col + 1]) { int temp = arr[col + 1]; arr[col + 1] = arr[col]; arr[col] = temp; flag = 0; } } if (flag == 1) { break; } } } 快速排序 快速排序一共分为三大步。 1、选择一个基准值:基准值就是参考的一个数。这个基准值我们一般选取最左边或者最右边,有助于下边的步骤进行。 2、遍历整个区间,把除基准值之外的所有数据与基准值进行比较,并进行数据移动,满足 1>比基准值小的数放在基准值的左边 2>比基准值大的数放在基准值的右边 (一开始的基准值不是在最左边或者最右边吗,怎么把数据放在它的左右呢?这个然会有函数处理) 3、分治算法:利用递归,让基准值的左右边的区间也重复上面的操作,直到区间的size为 0 或者 1。 ✦挖坑法 挖坑法和hover法差不多的。 //C语言 int partition_2(int arr[], int left, int right)//挖坑法 { int begin = left; int end = right; int pivot = arr[right];//保存了基准值 while (begin < end) { while (begin < end && arr[begin] = pivot) { --end; } arr[begin] = arr[end];//把end当成坑。 } arr[begin] = pivot;//把基准值 放入最后的坑 return begin; }
为了防止一比到底,导致最后一个数没有比较。 例如:1 3 4 2 假设1是基准值,从2开始,即就是end 这个时候一直是--end,直到遇见begin。但是begin上的元素是1,但退出循环后,会和基准值进行交换,但是arr[begin]没有和基准值进行比较。造成 小于基准值的数也放到了右边 2>arr[begin] = right) { return; } int povit = partition_3(arr, left, right);//用的前后下标法 QuickSort(arr, left, povit - 1);//递归调用 QuickSort(arr, povit + 1, right); } void Quick_Sort(int arr[], int size) { QuickSort(arr, 0 , size -1); }上面的快速排序,是个通俗易懂的版本,比较繁琐,把步骤分开了说。当然有精简版,但重要的应该是理解。上述递归也可以用循环加栈的方式。 归并排序 归并排序也需要借助分治算法。但是这个的基准值是一直是数组的中间那个数,而不是像快速排序一样选边上的数据作为基准值。 因为编辑器的原因,图只能这个样子了。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |