C++中的23种算法

核心提示：排序前：95 27 90 49 80 58 6 9 18 5027 90 49 80 58 6 9 18 50 [95] 95浮出27 49 80 58 6 9 18 50 [90 95] 90浮出27 49 58 6 9 18 50 [80 90 95] 80浮出27 49 6 9 18 50 [58 80 90 9

排序前：95 27 90 49 80 58 6 9 18 50

27 90 49 80 58 6 9 18 50 [95] 95浮出

27 49 80 58 6 9 18 50 [90 95] 90浮出

27 49 58 6 9 18 50 [80 90 95] 80浮出

27 49 6 9 18 50 [58 80 90 95] ......

27 6 9 18 49 [50 58 80 90 95] ......

6 9 18 27 [49 50 58 80 90 95] ......

6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束

在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的

i+2至n已经排序完毕，这也增进了气泡排序的效率。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX 10

#define SWAP(x,y) {int t; t = x; x = y; y = t;}

void selsort(int[]); // 选择排序

void insort(int[]); // 插入排序

void bubsort(int[]); // 气泡排序

int main(void) {

int number[MAX] = {0};

int i;

srand(time(NULL));

printf("排序前：");

for(i = 0; i < MAX; i++) {

number[i] = rand() % 100;

printf("%d ", number[i]);

}

printf("\n请选择排序方式：\n");

printf("(1)选择排序\n(2)插入排序\n(3)气泡排序\n:");

scanf("%d", &i);

switch(i) {

case 1:

selsort(number); break;

case 2:

insort(number); break;

case 3:

bubsort(number); break;

default:

printf("选项错误(1..3)\n");

}

return 0;

}

void selsort(int number[]) {

int i, j, k, m;

for(i = 0; i < MAX-1; i++) {

m = i;

for(j = i+1; j < MAX; j++)

if(number[j] < number[m])

m = j;

if( i != m)

SWAP(number[i], number[m])

printf("第%d 次排序：", i+1);

for(k = 0; k < MAX; k++)

printf("%d ", number[k]);

printf("\n");

}

}

void insort(int number[]) {

int i, j, k, tmp;

for(j = 1; j < MAX; j++) {

tmp = number[j];

i = j - 1;

while(tmp < number[i]) {

number[i+1] = number[i];

i--;

if(i == -1)

break;

}

number[i+1] = tmp;

printf("第%d 次排序：", j);

for(k = 0; k < MAX; k++)

printf("%d ", number[k]);

printf("\n");

}

}

void bubsort(int number[]) {

int i, j, k, flag = 1;

for(i = 0; i < MAX-1 && flag == 1; i++) {

flag = 0;

for(j = 0; j < MAX-i-1; j++) {

if(number[j+1] < number[j]) {

SWAP(number[j+1], number[j]);

flag = 1;

}

}

printf("第%d 次排序：", i+1);

for(k = 0; k < MAX; k++)

printf("%d ", number[k]);

printf("\n");

}

}

14.排序法-

改良的插入排序

说明

插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速

度不快。

排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加

快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。

解法

Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时