插入排序

#include<stdio.h>
#include<stdio.h>
#include<windows.h>
#define MAXSIZE 21
int defaultDate[] = {-9999,67,33,44,55,22,90,56,34,78,0};

void Insertsort1(int dataHandle[], int n);     //找到正确的位置后成批移动
void Insertsort2(int dataHandle[], int n);     //边比较边移动
void Insertsort3(int dataHandle[], int n);     //启动两个数据交换的函数

/*
通过找到已排空间中的一个正确位置，把待排空间的第一个数据插入到该位置
*/

void Insertsort1(int dataHandle[], int n) {
    int i, j,k, countTraverse;
    int timeMove = 0;          //记录一下移动的次数
      int timeCompare = 0;       //记录一下比较的次数
     for (int i = 2; i <= n; i++) {     //从前到后逐个取出 和前面的比较
        for (j = i - 1; j >= 1; j--) {
            timeCompare++;
            if (dataHandle[j] < dataHandle[i]) {     //如果取出的比前面的小 就记录位置
                break;
            }
        }
        //如果找到了一个合适的位置
        if (j != i - 1) {
            //将比代排空间第一个数据更大的数据成批向后移动，而且是反向移动
            int temp = dataHandle[i];
            timeMove++;
            for (k = i - 1; k > j; k--) {            
                dataHandle[k + 1] = dataHandle[k];
            }
            //代排空间的第一个数据放到指定空间上
            dataHandle[k + 1] = temp;
            //临时取出的数据放到排空的位置
            timeMove++;
            timeMove += i - j - 1;

            for (countTraverse = 1; countTraverse <= n; countTraverse++) {
                printf("%d ",dataHandle[countTraverse]);
            }
            printf("
");
        }
    }

    printf("一共比较了%d次。
",timeCompare);
    printf("移动的总次数为：%d
",timeMove);
}

/*
 对上面的排序思路进行改正，讲搜索和数据后移这两个步骤合并
*/
void Insertsort2(int dataHandle[], int n) {
    int i, j, k, countTraverse;
    int timeMove = 0;          
    int timeCompare = 0;
    for (i = 2; i <= n; i++) {
        if (dataHandle[i] < dataHandle[i - 1]) {
            timeCompare++;
            int temp = dataHandle[i];
            timeMove++;
            for (j = i - 1; i >= 1 && dataHandle[j] > temp; j--) {
                timeCompare++;
                dataHandle[j + 1] = dataHandle[j];
            }
            dataHandle[j + 1] = temp;
            timeMove++;
            timeMove = i - j - 1;

            for (countTraverse = 1; countTraverse <= n; countTraverse++) {
                printf("%d ", dataHandle[countTraverse]);
            }
            printf("
");
        }
    }
    printf("一共比较了%d次。
", timeCompare);
    printf("移动的总次数为：%d
", timeMove);
}


void Insertsort3(int dataHandle[], int n) {
    int i, j, k, countTraverse;
    int timeMove = 0;
    int timeCompare = 0;
    for (i = 2; i <= n; i++) {
        for (j = i - 1; i > 0 && dataHandle[j] > dataHandle[j + 1]; j--) {
            timeCompare++;
            int temp = dataHandle[j];
            dataHandle[j] = dataHandle[j + 1];
            dataHandle[j + 1] = temp;
            timeMove+=3;
        }
        if (j == i - 1) {
            timeCompare++;
        }
        for (countTraverse = 1; countTraverse <= n; countTraverse++) {
            printf("%d ", dataHandle[countTraverse]);
        }
        printf("
");
    }
    printf("一共比较了%d次。
", timeCompare);
    printf("移动的总次数为：%d
", timeMove);
}
int main(void) {

    SetConsoleTitle("插入排序的三种方式比较。");
    system("color f0");                  //设置背景为白色，字体为黑色


    Insertsort3(defaultDate,8);


    return 0;
}