首页 > 代码库 > C言语拔出排序算法及代码

C言语拔出排序算法及代码

拔出排序是排序算法的一种,它不改动原有的序列(数组),而是创立一个新的序列,在新序列长进行操作。
这里以从小到大排序为例停止解说。

根本思惟及举例阐明

拔出排序的根本思惟是,将元素逐一添加到曾经排序好的数组中去,同时请求,拔出的元素必需在准确的地位,如许本来排序好的数组是依然有序的。
在实践运用中,平日是排序全部无序数组,所以把这个无序数组分为两局部排序好的子数组和待拔出的元素。第一轮时,将第一个元素作为排序好的子数组,拔出第二个元素;第二轮,将前两个元素作为排序好的数组,拔出第三个元素。以此类推,第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<stdio.h> #include<stdlib.h> #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<n; i++) { //起首找到元素a[i]需求拔出的地位 int j=0; while( (a[j]<a[i]) && (j<i)) { 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<N; i++) printf("%d  ", num[i]); printf("\n"); system("pause"); return 0; }

留意:拔出排序是一种波动的排序算法,不会改动原有序列中相反数字的次序。
拔出排序是在一个曾经有序的弁言列的根底上,一次拔出一个元素。当然,刚开端这个有序的弁言列只要1个元素,就是第一个元素。比拟是从有序序列的末尾开端,也就是想要拔出的元素和曾经有序的最大者开端比起,假如比它大则直接拔出在厥后面,不然不断往前找直到找到它该拔出的地位。假如碰见一个和拔出元素相等的,那么拔出元素把想拔出的元素放在相等元素的前面。所以,相等元素的前后次序没有改动,从原无序序列出去的次序就是排好序后的次序,所以拔出排序是波动的。


本文出自 “11999725” 博客,请务必保留此出处http://12009725.blog.51cto.com/11999725/1843303

C言语拔出排序算法及代码