[数据结构与算法]C++选择，插入，希尔排序算法

#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
#define NUM 100000

void print(int* a,int len,bool is=true);

//选择排序
void select_sort(int* a,int len);
//插入排序
void insert_sort(int* a, int len);
//希尔排序
void shell_sort(int* a, int len);

void init(int* a);

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[] = { 9, 0, 5, 6, 4, 7, 8, 1, 3, 2 };
	int a[NUM];
#if NUM==10
	print(arr,NUM);

	shell_sort(arr, NUM);

	print(arr, NUM, 0);
#else
	init(a);//初始化数组

	clock_t oldTime, newTime;

	oldTime = clock();
	insert_sort(a, NUM);
	newTime = clock();
	printf("%d\n", newTime - oldTime);


	oldTime = clock();
	select_sort(a, NUM);
	newTime = clock();
	printf("%d\n", newTime - oldTime);

	oldTime = clock();
	shell_sort(a, NUM);
	newTime = clock();
	printf("%d\n", newTime - oldTime);


#endif




	while (1);
	return 0;
}

void init(int* a){
	srand(time(NULL));
	for (int i = 0; i < NUM; i++)
		a[i] = rand() % NUM;
}


void print(int* a, int len, bool is){
	if (is==0){
		printf("after  sort:");
	}
	if (is > 0){
		printf("before sort:");
	}

	for (int i = 0; i < len; i++)
		printf("%d ", a[i]);

	printf("\n");
}

//选择排序
void select_sort(int* a, int len){
	printf("选择排序!\n");

	//总共len-1次
	int minIdx;
	int temp;
	for (int i = 0; i < len - 1; i++){
		//1 从  a[i]  到  a[len - 1] 选出最小的
		minIdx = i;
		for (int j = i; j < len; j++){
			//if (a[minIdx] > a[j]){minIdx = j;}
			minIdx = (a[minIdx]<a[j]) ? minIdx : j;
		}
		//2 和 a[i]交换
		if (minIdx != i){
			temp = a[minIdx];
			a[minIdx] = a[i];
			a[i] = temp;
		}
		//print(a, NUM,-1);
	}



}

//插入排序
void insert_sort(int* a, int len){
	printf("插入排序!\n");
	int temp;
	int idx;//待插位置
	//插入len-1次   第 n 次插入下标为 n 的数据
	for (int i = 1; i < len; i++){
		//1 临时存储待插数据
		temp = a[i];
		//2 定位要插入位置，并且把要插入位置之后的数据后移
		
		/*
		idx = i;
		while (idx >= 0){//循环之后  idx就是要插入位置
			if (a[idx]>=temp)
				idx--;
			else
				break;
		}
		for (int j = i-1; j > idx; j--)//把要插入位置之后的数据后移
			a[j + 1] = a[j];
		*/
		idx = i-1;
		while (idx >= 0 && a[idx] > temp){
			a[idx + 1] = a[idx];
			idx--;
		}
		//3 待插数据赋值到要插入位置上
		a[idx + 1] = temp;
		//print(a, len, -1);
	}


}

//希尔排序
void shell_sort(int* a, int len){
	printf("希尔排序!\n");

	int step = (len >> 1);
	int temp;
	int idx;//待插位置
	while (step >= 1){
		for (int i = step; i < len; i++){
			//1 临时存储待插数据
			temp = a[i];
			//2 定位要插入位置，并且把要插入位置之后的数据后移
			idx = i - step;
			while (idx >= 0 && a[idx] > temp){
				a[idx + step] = a[idx];
				idx-=step;
			}
			//3 待插数据赋值到要插入位置上
			a[idx + step] = temp;
			
		}


		step >>= 1;//步长变为原来的一半
		//print(a, len, -1);
	}


}