八大排序算法是什么

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

void print(int a[], int n ,int i){

    cout<<i <<":";

    for(int j= 0; j<8; j++){

        cout<<a[j] <<" ";

    }

    cout<<endl;

}

void InsertSort(int a[], int n)

{

    for(int i= 1; i<n; i++){

        if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入

            int j= i-1;

            int x = a[i];        //复制为哨兵，即存储待排序元素

            a[i] = a[i-1];           //先后移一个元素

            while(x < a[j]){  //查找在有序表的插入位置

                a[j+1] = a[j];

                j--;         //元素后移

            }

            a[j+1] = x;      //插入到正确位置

        }

        print(a,n,i);           //打印每趟排序的结果

    }

}

int main(){

    int a[8] = {3,1,5,7,2,4,9,6};

    InsertSort(a,8);

    print(a,8,8);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

void print(int a[], int n ,int i){

    cout<<i <<":";

    for(int j= 0; j<8; j++){

        cout<<a[j] <<" ";

    }

    cout<<endl;

}

/**

 * 直接插入排序的一般形式

 *

 * @param int dk 缩小增量，如果是直接插入排序，dk=1

 *

 */

void ShellInsertSort(int a[], int n, int dk)

{

    for(int i= dk; i<n; ++i){

        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入

            int j = i-dk;  

            int x = a[i];           //复制为哨兵，即存储待排序元素

            a[i] = a[i-dk];         //首先后移一个元素

            while(x < a[j]){     //查找在有序表的插入位置

                a[j+dk] = a[j];

                j -= dk;             //元素后移

            }

            a[j+dk] = x;            //插入到正确位置

        }

        print(a, n,i );

    }

}

/**

 * 先按增量d（n/2,n为要排序数的个数进行希尔排序

 *

 */

void shellSort(int a[], int n){

    int dk = n/2;

    while( dk >= 1  ){

        ShellInsertSort(a, n, dk);

        dk = dk/2;

    }

}

int main(){

    int a[8] = {3,1,5,7,2,4,9,6};

    //ShellInsertSort(a,8,1); //直接插入排序

    shellSort(a,8);           //希尔插入排序

    print(a,8,8);

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

void print(int a[], int n ,int i){

    cout<<"第"<<i+1 <<"趟 : ";

    for(int j= 0; j<8; j++){

        cout<<a[j] <<"  ";

    }

    cout<<endl;

}

/**

 * 数组的最小值

 *

 * @return int 数组的键值

 */

int SelectMinKey(int a[], int n, int i)

{

    int k = i;

    for(int j=i+1 ;j< n; ++j) {

        if(a[k] > a[j]) k = j;

    }

    return k;

}

/**

 * 选择排序

 *

 */

void selectSort(int a[], int n){

    int key, tmp;

    for(int i = 0; i< n; ++i) {

        key = SelectMinKey(a, n,i);           //选择最小的元素

        if(key != i){

            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换

        }

        print(a,  n , i);

    }

}

int main(){

    int a[8] = {3,1,5,7,2,4,9,6};

    cout<<"初始值：";

    for(int j= 0; j<8; j++){

        cout<<a[j] <<"  ";

    }

    cout<<endl<<endl;

    selectSort(a, 8);

    print(a,8,8);

}