插入排序

pwnmelife

#include "pch.h"
#include <iostream>
#include <stdlib.h>

void Insert_Sort(int k[], int n);
void Binary_Insert_Sort(int k[], int n);
void Shell_Sort(int k[], int n);
int d[] = { 5,3,1 };
int main()
{
        int k[] = {50,26,38,80,70,90,8,30,40,20};
        Shell_Sort(k,10);
        printf("The sorted result: \n");
        for (int i = 0; i < 10; i++) {
                printf("%d ", k[i]);
        }
        printf("\n\n");
}

/*直接插入排序*/
void Insert_Sort(int k[], int n) {
        int temp,i,j;
        for (i = 1; i < n; i++) {
                if (k[i] < k[i - 1]) {
                        temp = k[i];
                        for (j = i - 1; temp < k[j] && j>=0; j--) {
                                k[j + 1] = k[j];
                        }
                        k[j+1] = temp;
                }
        }
}
/*折半插入排序*/
void Binary_Insert_Sort(int k[], int n) {
        
        int middle;
        int i, j,temp;
        for (i = 1; i < n; i++) {
                int low = 0;
                int high = i - 1;
                temp = k[i];
                while (low <= high) {
                        middle = (low + high) / 2;
                        if (k[middle] < temp) {
                                low = middle + 1;
                        }
                        else if(k[middle] > temp) {
                                high = middle - 1;
                        }
                        else {
                                break;
                        }
                }
                for (j = i - 1; j > high; j--) {
                        k[j + 1] = k[j];
                }
                k[high + 1] = temp;
        }
}
/*希尔排序*/
void Shell_Sort(int k[], int n) {
        int i, j, l, temp;
        for (i = 0; i < 3; i++) {
                for (j = d[i]; j < n; j++) {
                        if (k[j] < k[j - d[i]]) {
                                temp = k[j];
                                for (l = j - d[i]; k[l] > temp; l-=d[i]) {
                                        k[l + d[i]] = k[l];
                                }
                                k[l + d[i]] = temp;
                        }
                }
        }
}