选择排序是排序算法的一种,这里以从小到大排序为例进行讲解。
基本思想及举例说明
(了解)选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置;然后,选出第二小的数,放在第二个位置;以此类推,直到所有的数从小到大排序。(不稳定的算法)
在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换。
下面,以对3 2 4 1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置。
第1轮排序过程(寻找第1小的数所在的位置)
3 2
4 1(最初,min_index=1)
3 2
4 1(3 > 2,所以min_index=2)
3 2
4 1(2 < 4,所以min_index=2)
3 2
4 1(2 > 1,所以min_index=4,这时候确定了第1小的数在位置4)
1 2 4 3 (第1轮结果,将3和1交换,也就是位置1和位置4交换)
第2轮排序过程(寻找第2小的数所在的位置)
1 2 4 3(第1轮结果,min_index=2,只需要从位置2开始寻找)
1 2 4 3(4 > 2,所以min_index=2)
1 2 4 3(3 > 2,所以min_index=2)
1 2 4 3(第2轮结果,因为min_index位置刚好在第2个位置,无需交换)
第3轮排序过程(寻找第3小的数所在的位置)
1 2 4 3(第2轮结果,min_index=3,只需要从位置2开始寻找)
1 2 4 3(4 > 3,所以min_index=4)
1 2 3 4(第3轮结果,将3和4交换,也就是位置4和位置3交换)
至此,排序完毕。
总结及实现
选择排序对大小为N的无序数组R[N]进行排序,进行N-1轮选择过程。第i轮选取第i小的数,并将其放在第i个位置上。当第N-1次完成时,第N小(也就是最大)的数自然在最后的位置上。
下面给出选择排序的C语言实现。
#include
#include
#define N 8
void select_sort(int a[],int n);//实现数组选择排序的子程序
//选择排序实现
void select_sort(int a[],int n)//n为数组a的元素个数
{
//进行N-1轮选择
for(int i=0; i { int min_index = i; //找出第i小的数所在的位置 for(int j=i+1; j { if(a[j] < a[min_index]) { min_index = j; } } //将第i小的数,放在第i个位置;如果刚好,就不用交换 if( i != min_index) { int temp = a[i]; a[i] = a[min_index]; a[min_index] = temp; } } } int main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; select_sort(num, N); for(int i=0; i printf("%d ", num[i]); printf("\n"); system("pause"); return 0; } 注意:选择排序是一种不稳定的排序算法,可能会打乱两个相同数字的原有顺序。 例如,序列5 8 5 2 9,按照从小到大排序,第一轮会将第1个数字5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序是一种不稳定的排序算法 冒泡排序是排序算法的一种,思路清晰,代码简洁,常被用在大学生计算机课程中。 “冒泡”这个名字的由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。 这里以从小到大排序为例进行讲解。 基本思想及举例说明 冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移。经过一轮比较,就选出最大的数;经过第2轮比较,就选出次大的数,以此类推。(步骤较多,繁琐) 下面以对3 2 4 1 进行冒泡排序说明。 第一轮排序过程 3 2 4 1 (最初) 2 3 4 2 (比较3和2,交换) 2 3 4 1 (比较3和4,不交换) 2 3 1 4 (比较4和1,交换) 第一轮结束,最大的数4已经在最后面,因此第二轮排序只需要对前面三个数进行再比较。 第二轮排序过程 2 3 1 4 (第一轮排序结果) 2 3 1 4 (比较2和3,不交换) 2 1 3 4 (比较3和1,交换 第二轮结束,第二大的数已经排在倒数第二个位置,所以第三轮只需要比较前两个元素。 第三轮排序过程 2 1 3 4 (第二轮排序结果) 1 2 3 4 (比较2和1,交换) 至此,排序结束。 算法总结及实现 对于具有N个元素的数组R[n],进行最多N-1轮比较; 第一轮,逐个比较(R[1], R[2]), (R[2], R[3]), (R[3], R[4]), …….(R[N-1], R[N]); 最 大的元素会被移动到R[N]上。 第二轮,逐个比较(R[1], R[2]), (R[2], R[3]), (R[3], R[4]), …….(R[N-2], R[N-1]);第二大元素会被移动到R[N-1]上。 。。。。 以此类推,直到整个数组从小到大排序。 下面给出了冒泡排序的一般实现和优化实现。一般实现是教科书里常见的实现方法,无论数组是否排序好了,都会进行N-1轮比较;而优化实现,在数组已经排序好的情况下,会提前退出比较,减小了算法的时间复杂度。 #include #include #define N 8 void bubble_sort(int a[],int n); //一般实现 void bubble_sort(int a[],int n)//n为数组a的元素个数 { //一定进行N-1轮比较 for(int i=0; i { //每一轮比较前n-1-i个,即已排序好的最后i个不用比较 for(int j=0; j { if(a[j] > a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } } } //优化实现 void bubble_sort_better(int a[],int n)//n为数组a的元素个数 { //最多进行N-1轮比较 for(int i=0; i { bool isSorted = true; //每一轮比较前n-1-i个,即已排序好的最后i个不用比较 for(int j=0; j { if(a[j] > a[j+1]) { isSorted = false; int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } if(isSorted) break; //如果没有发生交换,说明数组已经排序好了 } } int main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; bubble_sort(num, N); //或者使用bubble_sort_better(num, N); for(int i=0; i printf("%d ", num[i]); printf("\n"); system("pause"); return 0; } 插入排序是排序算法的一种,它不改变原有的序列(数组),而是创建一个新的序列,在新序列上进行操作。 这里以从小到大排序为例进行讲解。 基本思想及举例说明 插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的。 在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时,将第一个元素作为排序好的子数组,插入第二个元素;第二轮,将前两个元素作为排序好的数组,插入第三个元素。以此类推,第i轮排序时,在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。 下面,以对3 2 4 1 进行选择排序说明插入过程,使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。 第1轮 [ 3 ] [ 2 4 1 ] (最初状态,将第1个元素分为排序好的子数组,其余为待插入元素)[ 3 ] [ 2 4 1 ] (由于3>2,所以待插入位置j=1) [ 2 3 ] [ 4 1 ] (将2插入到位置j) 第2轮 [ 2 3 ] [ 4 1 ] (第1轮排序结果) [ 2 3 ] [ 4 1 ] (由于2<4,所以先假定j=2) [ 2 3 ] [ 4 1 ] (由于3<4,所以j=3) [ 2 3 4 ] [ 1 ] (由于4刚好在位置3,无需插入) 第3轮 [ 2 3 4 ] [ 1 ] (第2轮排序结果) [ 2 3 4 ] [ 1 ] (由于1<2,所以j=1) [1 2 3 4 ] (将1插入位置j,待排序元素为空,排序结束) 算法总结及实现 选择排序对大小为N的无序数组R[N]进行排序,进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组,然后将剩余的N-1个元素,逐个插入到已经排序好子数组;。因此,在第i轮排序时,前i个元素总是有序的,将第i+1个元素插入到正确的位置。 #include #include #define N 8 void insert_sort(int a[],int n); //插入排序实现,这里按从小到大排序 void insert_sort(int a[],int n)//n为数组a的元素个数 { //进行N-1轮插入过程 for(int i=1; i { //首先找到元素a[i]需要插入的位置 int j=0; while( (a[j] { j++; } //将元素插入到正确的位置 if(i != j) //如果i==j,说明a[i]刚好在正确的位置 { int temp = a[i]; for(int k = i; k > j; k--) { a[k] = a[k-1]; } a[j] = temp; } } } int main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; insert_sort(num, N); for(int i=0; i printf("%d ", num[i]); printf("\n"); system("pause"); return 0; } 注意:插入排序是一种稳定的排序算法,不会改变原有序列中相同数字的顺序。 插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。 快速排序是对冒泡法排序的一种改进。 快速排序算法的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到所有要进行排序的数据变为有序为止。 可能仅根据基本思想对快速排序的认识并不深,接下来以对n个无序数列A[0], A[1]…, A[n-1]采用快速排序方法进行升序排列为例进行讲解。 (1)定义两个变量low和high,将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次,low和high的取值分别为0和n-1,接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。 (2)定义一个变量key,接下来以key的取值为基准将数组A划分为左右两个部分,通常,key值为要进行排序序列的第一个元素值。第一次的取值为A[0],以后毎次取值由要划分序列的起始元素决定。 (3)从high所指向的数组元素开始向左扫描,扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作,直到high不大于low或找到第一个小于基准值key的数组元素,然后将该值赋值给low所指向的数组元素,同时将low右移一个位置。 (4)如果low依然小于high,那么由low所指向的数组元素开始向右扫描,扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作,直到low不小于high或找到第一个大于基准值key的数组元素,然后将该值赋给high所指向的数组元素,同时将high 左移一个位置。 (5)重复步骤(3) (4),直到low的植不小于high为止,这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high],其中,pos下标所对应的数组元素的值就是进行划分的基准值key,所以在划分结束时还要将下标为pos的数组元素赋值为key。 (6)将划分得到的左右两部分A[low……pos-1]和A[pos+1……high]继续采用以上操作步骤进行划分,直到得到有序序列为止。 为了能够加深读者的理解,接下来通过一段代码来了解快速排序的具体实现方法。 #include #include #define N 6 int partition(int arr[], int low, int high){ int key; key = arr[low]; while(low while(low high--; if(low arr[low++] = arr[high]; while( low low++; if(low arr[high--] = arr[low]; } arr[low] = key; return low; } void quick_sort(int arr[], int start, int end){ int pos; if (start pos = partition(arr, start, end); quick_sort(arr,start,pos-1); quick_sort(arr,pos+1,end); } return; } int main(void){ int i; int arr[N]={32,12,7, 78, 23,45}; printf("排序前\n"); for(i=0;i printf("%d\t",arr[i]); quick_sort(arr,0,N-1); printf("\n 排序后\n"); for(i=0; i printf("%d\t", arr[i]); printf ("\n"); system("pause"); return 0; } 运行结果: 排序前 32 12 7 78 23 45 排序后 7 12 23 32 45 78 在上面的代码中,根据前面介绍的步骤一步步实现了快速排序算法。接下来通过示意图来演示第一次划分操作。 在第一次划分操作中,先进行初始设置,key的值是进行划分的基准,其值为要划分数组的第一个元素值,在上面的排序序列中为第一个元素值32,同时将low设置为要排序数组中第一个元素的下标,第一次排序操作时其值为0,将high设置为要排序序列最后一个元素的下标,在上面的排序序列中其第一次取值为5。先将下标为high的数组元素与key进行比较,由于该元素值大于key,因此high向左移动一个位置继续扫描。由于接下来的值为23,小于key的值,因此将23赋值给下标为low所指向的数组元素。接下来将low右移一个位置,将low所指向的数组元素的值与key进行比较,由干接下来的12、7都小于key,因此low继续右移扫描,直至下标low所指向的数组元素的值为78即大于key为止,将78赋值给下标为high所指向的数组元素,同时将high左移一个位置。接下来由于low不再小于high,划分结束。需要注意的是,在进行划分的过程中,都是将扫描的值与key的值进行对比,如果小于key,那么将该值赋值给数组中的另外一个元素,而该元素的值并没有改变。从图中可以看出这一点,所以需要在划分的最后将作为划分基准的key值赋值给下标为pos的数组元素,这个元素不再参与接下来的划分操作。 第一轮划分结束后,得到了左右两部分序列A[0]、A[1]、A[2]和A[4]、A[5],继续进行划分,即对毎轮划分后得到的两部分序列继续划分,直至得到有序序列为止。 归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并。仅从算法思想上了解归并排序会觉得很抽象,接下来就以对序列A[0], A[l]…, A[n-1]进行升序排列来进行讲解,在此采用自顶向下的实现方法,操作步骤如下。 (1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first … mid]和A[mid+1 … last]。 (2)将上面所分得的两部分序列继续按照步骤(1)继续进行划分,直到划分的区间长度为1。 (3)将划分结束后的序列进行归并排序,排序方法为对所分的n个子序列进行两两合并,得 到n/2或n/2+l个含有两个元素的子序列,再对得到的子序列进行合并,直至得到一个长度为n的有序序列为止。下面通过一段代码来看如何实现归并排序。 #include #include #define N 7 void merge(int arr[], int low, int mid, int high){ int i, k; int *tmp = (int *)malloc((high-low+1)*sizeof(int)); //申请空间,使其大小为两个 int left_low = low; int left_high = mid; int right_low = mid + 1; int right_high = high; for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比较两个指针所指向的元素 if(arr[left_low]<=arr[right_low]){ tmp[k] = arr[left_low++]; }else{ tmp[k] = arr[right_low++]; } } if(left_low <= left_high){ //若第一个序列有剩余,直接复制出来粘到合并序列尾 //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int)); for(i=left_low;i<=left_high;i++) tmp[k++] = arr[i]; } if(right_low <= right_high){ //若第二个序列有剩余,直接复制出来粘到合并序列尾 //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int)); for(i=right_low; i<=right_high; i++) tmp[k++] = arr[i]; } for(i=0; i arr[low+i] = tmp[i]; free(tmp); return; } void merge_sort(int arr[], unsigned int first, unsigned int last){ int mid = 0; if(first mid = (first+last)/2; /* 注意防止溢出*/ /*mid = first/2 + last/2;*/ //mid = (first & last) + ((first ^ last) >> 1); merge_sort(arr, first, mid); merge_sort(arr, mid+1,last); merge(arr,first,mid,last); } return; } int main(){ int i; int a[N]={32,12,56,78,76,45,36}; printf ("排序前\n"); for(i=0;i printf("%d\t",a[i]); merge_sort(a,0,N-1); // 排序 printf ("\n 排序后\n"); for(i=0;i printf("%d\t",a[i]); printf("\n"); system("pause"); return 0; } 运行结果: 排序前 32 12 56 78 76 45 36 排序后 12 32 36 45 56 76 78 分析上面的运行结果,通过归并排序成功地实现了对给定序列的排序操作。接下来通过图11-9来了解归并排序的具体操作流程。 在图11-9中,先对所要进行排序的序列进行分解,直到分为单个元素为止,然后将其进行两两合并。由于最终分解成单个元素,因此在合并的时候.将小数放在前面,大数放在后面,得到一个有序序列。接下来对两个相连的有序序列进行排序,先比较有序序列中的第一个元素,将较小的元素放入临时数组中,接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较,同样将较小元素放入临时数组中,依次进行,直到两个数组的所有元素都放入临时数组中,最后再将临时数组的元素放入原始数组中的对应位置。 顺序査找是一种简单的査找算法,其实现方法是从序列的起始元素开始,逐个将序列中的元素与所要查找的元素进行比较,如果序列中有元素与所要查找的元素相等,那么査找成功,如果査找到序列的最后一个元素都不存在一个元素与所要査找的元素值相等,那么表明査找失败。接下来通过一段代码来了解顺序査找的具体使用。 #include #include #include int ordersearch(int a[], int n, int des){ int i; for(i=0; i if(des==a[i]) return 1; return 0; } int main(){ int i, val; int a[8] = {32,12,56,78,76,45,43,98}; int ret; for(i=0; i<8; i++) printf("%d\t", a[i]); printf("\n请输入所要查找的元素:"); while(1){ scanf("%d", &val); fflush(stdin); ret = ordersearch(a, 8, val); if(1 == ret) printf ("查找成功!"); else printf ("查找失败!"); printf("\n请输入所要查找的元素:"); } return 0; } 运行结果: 32 12 56 78 76 45 43 98 请输出所要查找的元素:78 查找成功! 请输出所要查找的元素:5 查找失败! 分析上面的运行结果,首先输入所要查找的元素为78,该数在所要查找的序列中是存在的,所以打印输出“查找成功!”。接下来输入的数值5在所要查找的序列中并不存在,因此打印输出“查找失败!”。 二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列。该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分。接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解。 #include binarySearch(int a[], int n, int key){ int low = 0; int high = n - 1; while(low<= high){ int mid = (low + high)/2; int midVal = a[mid]; if(midVal low = mid + 1; else if(midVal>key) high = mid - 1; else return mid; } return -1; } int main(){ int i, val, ret; int a[8]={-32, 12, 16, 24, 36, 45, 59, 98}; for(i=0; i<8; i++) printf("%d\t", a[i]); printf("\n请输人所要查找的元素:"); scanf("%d",&val); ret = binarySearch(a,8,val); if(-1 == ret) printf("查找失败\n"); else printf ("查找成功\n"); return 0; } 运行结果: -32 12 16 24 36 45 59 98 请输入所要查找的元素:12 查找成功 在上面的代码中,我们成功地通过二分査找算法实现了查找功能,其实现过程如下图所示。 在如上图所示的查找过程中,先将序列中间位置的元素与所要査找的元素进行比较,发现要査找的元素位干该位置的左部分序列中。接下来将mid的左边一个元素作为high,继续进行二分査找,这时mid所对应的中间元素刚好是所要査找的元素,査找结束,返回査找元素所对应的下标。在main函数中通过返回值来判断査找是否成功,如果査找成功.就打印输出“査找成功”的信息,否则输出“査找失畋”的信息。 C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的: 首先新建一个空列表,用于保存已排序的有序数列(我们称之为"有序列表")。 从原数列中取出一个数,将其插入"有序列表"中,使其仍旧保持有序状态。 重复2号步骤,直至原数列为空。 插入排序的平均时间复杂度为平方级的,效率不高,但是容易实现。它借助了"逐步扩大成果"的思想,使有序列表的长度逐渐增加,直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的: 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。 重复2号步骤,直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法。 选择排序 选择排序是这样实现的: 设数组内存放了n个待排数字,数组下标从1开始,到n结束。 i=1 从数组的第i个元素开始到第n个元素,寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n-1算法结束,否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始,我们要接触高效排序算法了。实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。这是一种先进的思想,也是它高效的原因。因为在排序算法中,算法的高效与否与列表中数字间的比较次数有直接的关系,而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了,大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同,它是这样的: 首先新建一个空列表,作用与插入排序中的"有序列表"相同。 找到数列中最大的数字,将其加在"有序列表"的末尾,并将其从原数列中删除。 重复2号步骤,直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高(因为有堆这种数据结构以及它奇妙的特征,使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度,维护需要logn的时间复杂度),但是实现相对复杂(可以说是这里7种算法中比较难实现的)。 C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子:乱序输入n个数,输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 一、设计思想 插入排序:首先,我们定义我们需要排序的数组,得到数组的长度。如果数组只有一个数字,那么我们直接认为它已经是排好序的,就不需要再进行调整,直接就得到了我们的结果。否则,我们从数组中的第二个元素开始遍历。然后,启动主索引,我们用curr当做我们遍历的主索引,每次主索引的开始,我们都使得要插入的位置(insertIndex)等于-1,即我们认为主索引之前的元素没有比主索引指向的元素值大的元素,那么自然主索引位置的元素不需要挪动位置。然后,开始副索引,副索引遍历所有主索引之前的排好的元素,当发现主索引之前的某个元素比主索引指向的元素的值大时,我们就将要插入的位置(insertIndex)记为第一个比主索引指向元素的位置,跳出副索引;否则,等待副索引自然完成。副索引遍历结束后,我们判断当前要插入的位置(insertIndex)是否等于-1,如果等于-1,说明主索引之前元素的值没有一个比主索引指向的元素的值大,那么主索引位置的元素不要挪动位置,回到主索引,主索引向后走一位,进行下一次主索引的遍历;否则,说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大,那么,我们记录当前主索引指向的元素的值,然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位,这里注意,要从后向前一位一位挪,否则,会使得数组成为一串相同的数字。最后,将记录下的当前索引指向的元素的值放在要插入的位置(insertIndex)处,进行下一次主索引的遍历。继续上面的工作,最终我们就可以得到我们的排序结果。插入排序的特点在于,我们每次遍历,主索引之前的元素都是已经排好序的,我们找到比主索引指向元素的值大的第一个元素的位置,然后将主索引指向位置的元素插入到该位置,将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法,使得挪动的次数相对较多,如果对于排序数据量较大,挪动成本较高的情况时,这种排序算法显然成本较高,时间复杂度相对较差,是初等通用排序算法中的一种。 选择排序:选择排序相对插入排序,是插入排序的一个优化,优化的前提是我们认为数据是比较大的,挪动数据的代价比数据比较的代价大很多,所以我们选择排序是追求少挪动,以比较次数换取挪动次数。首先,我们定义我们需要排序的数组,得到数组的长度,定义一个结果数组,用来存放排好序的数组,定义一个最小值,定义一个最小值的位置。然后,进入我们的遍历,每次进入遍历的时候我们都使得当前的最小值为9999,即认为每次最小值都是最大的数,用来进行和其他元素比较得到最小值,每次认为最小值的位置都是0,用来重新记录最小值的位置。然后,进入第二层循环,进行数值的比较,如果数组中的某个元素的值比最小值小,那么将当前的最小值设为元素的值,然后记录下来元素的位置,这样,当跳出循环体的时候,我们会得到要排序数组中的最小值,然后将最小值位置的数值设置为9999,即我们得到了最小值之后,就让数组中的这个数成为最大值,然后将结果数组result[]第主索引值位置上的元素赋值为最小值,进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于,我们挪动元素的次数很少,只是每次对要排序的数组进行整体遍历,找到其中的最小的元素,然后将改元素的值放到一个新的结果数组中去,这样大大减少了挪动的次序,即我们要排序的数组有多少元素,我们就挪动多少次,而因为每次都要对数组的所有元素进行遍历,那么比较的次数就比较多,达到了n2次,所以,我们使用选择排序的前提是,认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序,他的比较次数大于插入排序的次数,而挪动次数就很少,元素有多少个,挪动次数就是多少个。 希尔排序:首先,我们定义一个要排序的数组,然后定义一个步长的数组,该步长数组是由一组特定的数字组成的,步长数组具体得到过程我们不去考虑,是由科学家经过很长时间计算得到的,已经根据时间复杂度的要求,得到了最适合希尔排序的一组步长值以及计算C语言几种常见的排序方法
C语言9种常用排序法
几种排序算法的分析与比较--C语言
C语言的四种排序