插入排序

pwnmelife

1. #include "pch.h"
   
2. #include <iostream>
   
3. #include <stdlib.h>
   
4. 
   
5. void Insert_Sort(int k[], int n);
   
6. void Binary_Insert_Sort(int k[], int n);
   
7. void Shell_Sort(int k[], int n);
   
8. int d[] = { 5,3,1 };
   
9. int main()
   
10. {
    
11.         int k[] = {50,26,38,80,70,90,8,30,40,20};
    
12.         Shell_Sort(k,10);
    
13.         printf("The sorted result: \n");
    
14.         for (int i = 0; i < 10; i++) {
    
15.                 printf("%d ", k[i]);
    
16.         }
    
17.         printf("\n\n");
    
18. }
    
19. 
    
20. /*直接插入排序*/
    
21. void Insert_Sort(int k[], int n) {
    
22.         int temp,i,j;
    
23.         for (i = 1; i < n; i++) {
    
24.                 if (k[i] < k[i - 1]) {
    
25.                         temp = k[i];
    
26.                         for (j = i - 1; temp < k[j] && j>=0; j--) {
    
27.                                 k[j + 1] = k[j];
    
28.                         }
    
29.                         k[j+1] = temp;
    
30.                 }
    
31.         }
    
32. }
    
33. /*折半插入排序*/
    
34. void Binary_Insert_Sort(int k[], int n) {
    
35.        
    
36.         int middle;
    
37.         int i, j,temp;
    
38.         for (i = 1; i < n; i++) {
    
39.                 int low = 0;
    
40.                 int high = i - 1;
    
41.                 temp = k[i];
    
42.                 while (low <= high) {
    
43.                         middle = (low + high) / 2;
    
44.                         if (k[middle] < temp) {
    
45.                                 low = middle + 1;
    
46.                         }
    
47.                         else if(k[middle] > temp) {
    
48.                                 high = middle - 1;
    
49.                         }
    
50.                         else {
    
51.                                 break;
    
52.                         }
    
53.                 }
    
54.                 for (j = i - 1; j > high; j--) {
    
55.                         k[j + 1] = k[j];
    
56.                 }
    
57.                 k[high + 1] = temp;
    
58.         }
    
59. }
    
60. /*希尔排序*/
    
61. void Shell_Sort(int k[], int n) {
    
62.         int i, j, l, temp;
    
63.         for (i = 0; i < 3; i++) {
    
64.                 for (j = d[i]; j < n; j++) {
    
65.                         if (k[j] < k[j - d[i]]) {
    
66.                                 temp = k[j];
    
67.                                 for (l = j - d[i]; k[l] > temp; l-=d[i]) {
    
68.                                         k[l + d[i]] = k[l];
    
69.                                 }
    
70.                                 k[l + d[i]] = temp;
    
71.                         }
    
72.                 }
    
73.         }
    
74. }
    

复制代码