常用排序算法26550

1、常用排序算法总结及C源程序*直接插入排序*/*思想：先将有序序列中的第1个元素看作是有序序列的子序列，然后从第2个记录开始逐个进行插入*/*直至整个序列变成按关键字非递减的有序序列为止。*/void InsertSort(int *out, int *op, int length)int i, j;int data; memcpy(out, op, length * sizeof(int);for(i = 1; i length; i+)data = out;for(j = i-1; data =0; j-) outj+1 = outj;outj+1 = data;-/*折半插入排序*/*思想

2、：与折半查找类似*/void BInsertSort(int *out, int *op, int length)int low, mid, high; int i, j, data;memcpy(out, op, length * sizeof(int);for(i = 1; i length; i+)data = out;low = 0;high = i - 1;while(low = high) mid = (low+high) / 2; if(data = high+1; j-) outj+1 = outj;outj+1 = data;-/*冒泡算法*/*思想：*/*第一趟冒泡排序（比

3、较第1个到第n个记录）：*/*首先比较第1个元素和第2个元素的大小，若第1个比第2个小，则交换他们的值*/*接着比较第2个元素和第3个元素的大小直到第n-1和第n个元素*/*第二趟冒泡排序（比较第1个到第n-1个记录）*/void BubbleSort(int *out, int *op, int length)int i, j;memcpy(out, op, length * sizeof(int);for(i = length-1; i = 0; i-)for(j = 0; j outj+1) swap(out+j, out+j+1); -/*快速排序，对冒泡排序的一种改进*/*思想：通过

4、一趟排序，将待排记录分为独立的两部分，其中一部分记录的关键字均比另一部分的关键字小*/*则可对这两部分记录继续进行排序，以达到整个序列有序*/*一趟快速排序的做法*/*附设两个指针low,high，分别指向第1个记录和第n个记录，设关键字枢纽为pivokey,指向第一个记录*/*1.首先从high位置向前搜索，直到搜到比pivokey小的记录，与pivokey进行交换*/*2.从low位置向后搜索，知道搜到比pivokey大的记录，与pivokey进行交换*/*3.重复这两步，直到low = high为止*/int Partition(int *out, int *op, int length

5、, int low, int high)int pivokey;memcpy(out, op, length * sizeof(int);pivokey = outlow;while(low pivokey & low high) high-; swap(out+high, &pivokey); while(outlow pivokey & low high) low+; swap(out+low, &pivokey);return low;/递归形式的快速排序算法void QSort(int *out, int *op, int length, int low, int high)int p

6、ivoloc;memcpy(out, op, length * sizeof(int);if(low high)pivoloc = Partition(out, op, length, low, high); QSort(out, out, length, low, pivoloc-1); QSort(out, out, length, pivoloc+1, high);-/*选择排序思想：每一趟在n-i（i=0,1,.n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。*/*简单选择排序思想：一趟简单选择排序的操作为：通过n-i-1次关键字之间的比较，从n-i个记录中选取关键字最小

7、的记录，并和第i（1=i=n）个记录交换。*/从第i到第n个位置，找出n-i+1个记录中的最小值的位置。int SelectMinKey(int *op, int length, int i)int pos = i, j;int min = op;for(j = i + 1; j length; j+)if(opj min) min = opj; pos = j;return pos;/简单选择排序void SelectSort(int *out, int *op, int length)int i, j;memcpy(out, op, length * sizeof(int);for(i =

8、 0; i length; i+) j = SelectMinKey(out, length, i); if(i != j) swap(out+i, out+j); -/*希尔排序，又称：缩小增量排序*/*思路：先将整个待排序列分为几个子序列，分别进行直接插入排序，待整个序列中的记录基本有序时*/*再对全体记录进行一次直接插入排序*/void Shell(int *out, int *op, int length, int dk) /一趟希尔排序/与直接插入排序相比，前后记录位置的增量为dk，而不是1int i, j, data;memcpy(out, op, length * sizeof(int);for(i = dk; i length; i+)data = out;for(j = i-dk; (data =0; j=j-dk) outj+dk = outj;outj+dk = data;/按增量序列dlta0