三趟结果04 13 27 38 49 49 55 65 76 97 Shell排序的算法实现:1． 不设监视哨的算法描述void ShellPass(SeqList R,2.稳定性选择排序是给每个位置选择当前元素最小的,该趟排序从当前无序区中选出关键字最小的记录 R[k],②第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k],希尔排序怎么排啊下标 0 1 2 3 4 5 6 7 8 9数组 49 38 65 97 26 13 27 50 55 4 (原数组)增量=5, =49与=13为一组,互换为 13 49 (排序是从小到大) =38与=27为一组,互换为 27 38 =65与=50为一组,互换为 50 65 =97与=55为一组,互换为 55 97 =26与=4 为一组,互换为 4 26增量=5的排序结果是: 13 27 50 55 4 49 38 65 97 26下标 0 1 2 3 4 5 6 7 8 9数组 13 27 50 55 4 49 38 65 97 26 (第一趟之后)增量=2, =13,=50,=4,=38,=97为一组, 互换之后,=4,=13,=38,=50,=97 =27,=55,=49,=65,=26为一组, 互换之后,=26,=27,=49,=55,=65增量=2的排序结果是: 4 26 13 27 38 49 50 55 97 65下标 0 1 2 3 4 5 6 7 8 9数组 4 26 13 27 38 49 50 55 97 65 (第二趟之后)增量=1, 数组里的10个数据作为一组,其中, =26有=13互换为 13 26 =97与=65互换为 65 97增量=1的排序结果是: 4 13 26 27 38 49 50 55 65 97// C语言测试代码// 希尔排序法 (自定增量)#include 《stdio.h》#include 《stdlib.h》void printData(int data,int n) //打印数组{ int i; for(i=0;i《n;i++) { printf(“%d “,data[i]); } printf(“\n“);}//希尔排序(从小到大)void shell(int data,int count){ int offset_a={5,2,1}; //每一趟的增量 int len; int pos; int offset; int i,j; int temp; len=sizeof(offset_a)/sizeof(int); for(i=0;i《len;i++) { offset=offset_a[i]; for(j=offset;j《count;j++) { temp=data[j]; pos=j-offset; while(temp《data[pos] && pos》=0 && j《=count) { data[pos+offset]=data[pos]; pos=pos-offset; } data[pos+offset]=temp; } printf(“增量=%d,排序结果: “,offset); printData(data,count); }}int main(void){ int data={49,38,65,97,26,13,27,50,55,4}; int count; count=sizeof(data)/sizeof(int); printf(“原数组: “); printData(data,count); shell(data,count); printf(“\n最后的排序结果: “); printData(data,count); return 0;}选择排序的基本选择排序排序算法即解决以下问题的算法： 原序列的一个重排《a1*,a2*,a3*,...,an*》,让他跟数组中第二个元素交换一下值,即所有记录放在同一组中进行直接插入排序为止,我们知道第一遍选择第1个元素5会和2交换。
希尔排序怎么排啊
下标 0 1 2 3 4 5 6 7 8 9数组 49 38 65 97 26 13 27 50 55 4 (原数组)增量=5, =49与=13为一组,互换为 13 49 (排序是从小到大) =38与=27为一组,互换为 27 38 =65与=50为一组,互换为 50 65 =97与=55为一组,互换为 55 97 =26与=4 为一组,互换为 4 26增量=5的排序结果是: 13 27 50 55 4 49 38 65 97 26下标 0 1 2 3 4 5 6 7 8 9数组 13 27 50 55 4 49 38 65 97 26 (第一趟之后)增量=2, =13,=50,=4,=38,=97为一组, 互换之后,=4,=13,=38,=50,=97 =27,=55,=49,=65,=26为一组, 互换之后,=26,=27,=49,=55,=65增量=2的排序结果是: 4 26 13 27 38 49 50 55 97 65下标 0 1 2 3 4 5 6 7 8 9数组 4 26 13 27 38 49 50 55 97 65 (第二趟之后)增量=1, 数组里的10个数据作为一组,其中, =26有=13互换为 13 26 =97与=65互换为 65 97增量=1的排序结果是: 4 13 26 27 38 49 50 55 65 97// C语言测试代码// 希尔排序法 (自定增量)#include 《stdio.h》#include 《stdlib.h》void printData(int data,int n) //打印数组{ int i; for(i=0;i《n;i++) { printf(“%d “,data[i]); } printf(“\n“);}//希尔排序(从小到大)void shell(int data,int count){ int offset_a={5,2,1}; //每一趟的增量 int len; int pos; int offset; int i,j; int temp; len=sizeof(offset_a)/sizeof(int); for(i=0;i《len;i++) { offset=offset_a[i]; for(j=offset;j《count;j++) { temp=data[j]; pos=j-offset; while(temp《data[pos] && pos》=0 && j《=count) { data[pos+offset]=data[pos]; pos=pos-offset; } data[pos+offset]=temp; } printf(“增量=%d,排序结果: “,offset); printData(data,count); }}int main(void){ int data={49,38,65,97,26,13,27,50,55,4}; int count; count=sizeof(data)/sizeof(int); printf(“原数组: “); printData(data,count); shell(data,count); printf(“\n最后的排序结果: “); printData(data,count); return 0;}
选择排序的基本选择排序
排序算法即解决以下问题的算法： 原序列的一个重排《a1*,a2*,a3*,...,an*》；，使得a1*《=a2*《=a3*《=...《=an*排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：①初始状态：无序区为R[1..n]，有序区为空。②第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。……③第i趟排序第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。 1.时间复杂度选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。其他排序算法的复杂度如右图所示。2.稳定性选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
希尔排序的排序过程
希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。排序过程：先取一个正整数d1《n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2《d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。 三趟结果04 13 27 38 49 49 55 65 76 97 Shell排序的算法实现:1． 不设监视哨的算法描述void ShellPass(SeqList R，int d){//希尔排序中的一趟排序，d为当前增量for(i=d+1;i《=n；i++) //将R[d+1．．n]分别插入各组当前的有序区if(R[ i ].key《R[i-d].key){R=R[i];j=i-d； //R只是暂存单元，不是哨兵do {//查找R的插入位置R[j+d]=R[j]； //后移记录j=j-d； //查找前一记录}while(j》0&&R.key《R[j].key)；R[j+d]=R； //插入R到正确的位置上} //endif
什么是希尔排序
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。增量序列的取值依次为：5，3，1