// InsertSort.cpp : 定义控制台应用程序的入口点。//插值排序#include "stdafx.h"#include <cstdlib>static int testArray[] = {0,55,33,22,99,77,66,11,44,88,9};//11个//数组0号位置 作为 哨兵…//升序排序void insertSort(int * array,int num){for (int i = 2; i <= num; i++){if (array[i] < array[i-1]){array[0] = array[i];//复制哨兵.array[i] = array[i-1];int j = i – 2;for (; array[j] > array[0]; j–){//后移array[j+1] = array[j];}array[j+1] = array[0];}}}//折半插入排序void halfInsertSort(int *array,int num){for (int i = 2; i <= num; i++){array[0] = array[i];//复制哨兵int low = 1;int high = i-1;while (low <= high){int mid = (low + high)/2;if (array[mid] > array[0]){high = mid -1;}else{low = mid +1;}}int j = i – 1;for (; j >= high+1; j–){array[j+1] = array[j];}array[j+1] = array[0];}}//2路插入排序void p2_InsertSort(int * array,int num){int size = sizeof(int) * (num);int * p = (int *)malloc(size);int first = 0;int final = 0;p[0] = array[1];for (int i = 2; i <= num; i++){if (array[i] < p[first]){first = (first -1 + num) % num;p[first] = array[i];}else if(array[i] > p[final]){final = (final +1)% num;p[final] = array[i];}else{int j = final++;for (; p[j] > array[i] ; ){int index = (j+1)%num;p[index] = p[j];j = (j-1 + num ) % num;}p[(j+1)%num] = array[i];}}for (int i = 0; i < num; i++){int index = (first +i) % num;array[i+1] = p[index];}free(p);}void randomArray(){for (int i = 1; i <= 10; i++){testArray[i] = rand() % 100;}}void printArray(){for (int i = 1; i < 11; i++){printf("%d\t",testArray[i]);}printf("\n");}//静态表插入排序，，//不需要移动，只需要更改 next “指针”#define SIZE 100struct SLNode{int data;int next;};struct SLTable{//静态链表SLNode base[SIZE];int len;};//初始化静态链表void initTable(SLTable * t,int * array,int num){for (int i = 1; i <= num; i++){t->base[i].data = array[i];}t->base[1].next = 0;t->base[0].next = 1;t->base[0].data = INT_MAX;t->len = num;}void tableInsertSort(SLTable * t,int * array,int num){for (int i = 2; i <= num; i++){int pre = 0;int next = t->base[0].next;while (next != 0){SLNode node = t->base[next];if (node.data > array[i]){break;}pre = next;next = t->base[next].next;}t->base[i].next = t->base[pre].next;t->base[pre].next = i;}}void printTable(SLTable t){int next = t.base[0].next;while (next != 0){printf("%d\t",t.base[next].data);next = t.base[next].next;}}//shell 排序//缩小增量排序void shellInsert(int * array,int num,int dt){for (int i = dt + 1; i <= num; i++){if (array[i] < array[i-dt]){array[0] = array[i];int j = i – dt;for (;j > 0 && array[j] > array[0] ; j-=dt){array[j+dt] = array[j];}array[j+dt] = array[0];}}}static int dtArray[] = {5,3,2,1};void shellSort(int * array,int num){for (int i = 0; i < 4; i++){shellInsert(array,num,dtArray[i]);}}int _tmain(int argc, _TCHAR* argv[]){//srand(5000);//插入排序printf("—————-插入排序—————\n");randomArray();insertSort(testArray,10);printArray();//二分插入排序printf("—————-二分插入排序—————\n");randomArray();halfInsertSort(testArray,10);printArray();//二路插入排序printf("—————-二路插入排序—————\n");randomArray();p2_InsertSort(testArray,10);printArray();printf("—————-静态链表插入排序—————\n");randomArray();SLTable t;initTable(&t,testArray,10);tableInsertSort(&t,testArray,10);printTable(t);//shell sortprintf("—————-希尔排序—————\n");randomArray();shellSort(testArray,10);printArray();return 0;}
接受失败，是我们不常听到或看到的一个命题，
