排序

排序算法的分类：
1.插入排序–直接插入、折半插入、2路插入排序、表排序、希尔排序
2.交换排序–快速排序、冒泡排序
3.选择排序–堆排序、简单选择排序、树形选择排序
4.归并排序
5.基数排序(桶排序)

堆排序：只需要记录一个大小的辅助空间，每个带排序的记录仅占用一个存储空间。
堆是顺序表表示的完全二叉树，地址连续的一块空间。
物理内存上为顺序表，逻辑上是完全二叉树。
Ki<=K2i Ki <= K2i+1 (小顶堆) 或者 Ki>=K2i Ki>=K2i+1(大顶堆)

下面是各种排序算法的实现：

#include <stdio.h>
#include <stdlib.h>

/*插入排序:将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表*/
void insertion(int sort[], int n){
	int i, j;
	for ( i = 2; i <= n; i++){
		if (sort[i] < sort[i - 1]){
			sort[0] = sort[i];
			sort[i] = sort[i - 1];
			for ( j = i - 2; sort[0] < sort[j]; --j){
				sort[j + 1] = sort[j];
			}
			sort[j + 1] = sort[0];
		}
	}
}
/*折半插入排序*/
void BinInsertSort(int sort[], int n){
	int i,low,high,mid,j;
	for (i = 2; i <= n; ++i){
		sort[0] = sort[i];
		low = 1; high = i - 1;
		while(low <= high){
			mid = (low + high) / 2;
			if (sort[0] < sort[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; --j)
			sort[j + 1] = sort[j];
		sort[high + 1] = sort[0];
	}
}

/*二路插入排序：减少排序过程中移动记录的次数，但是需要n个记录的辅助空间。*/

/*表插入排序*/

/*希尔排序 又称 “缩小增量排序” ： 先将待排序记录序列分割成若干子序列分别进行直接插入排序，带整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。子序列的构成不是简单“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。*/
先将待排序记录序列分割成若干子序列分别进行直接插入排序，带整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
子序列的构成不是简单“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。*/
void ShellInsert(int sort[], int dk,int n){
	int i, j;
	for (i = dk + 1; i <= n; ++i){
		if (sort[i] < sort[i - dk]){
			sort[0] = sort[i];
			for (j = i - dk; j > 0 && sort[0] < sort[j]; j -= dk){
				sort[j + dk] = sort[j];
			}
			sort[j + dk] = sort[0];
		}
	}
}
void ShellSort(int sort[], int dlta[], int t){
	for (int k = 0; k < t; ++k){
		ShellInsert(sort, dlta[k], 10);
	}
}

/*冒泡排序*/
void bubble_sort(int sort[], int n){
	int j, temp;
	int chage = true;
	for (int i = n - 1; i >= 1 && chage; --i){
		chage = false;
		for (j = 0; j < i; ++j){
			if (sort[j] > sort[j + 1]){
				temp = sort[j];
				sort[j] = sort[j + 1];
				sort[j + 1] = temp;
			}
				chage = true;
		}
	}
}

/*快速排序:通过一趟排序将带排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两个部分继续进行排序，以达到整个序列有序。*/
其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对着两个部分继续进行排序，以达到整个序列有序。*/
int Partition(int sort[], int low, int high){
	int pivotkey = sort[low];
	sort[0] = sort[low];
	while (low < high){
		while (low < high && sort[high] >= pivotkey)
			--high;
		sort[low] = sort[high];
		while (low < high && sort[low] <= pivotkey)
			++low;
		sort[high] = sort[low];
	}
	sort[low] = sort[0];
	return low;
}
void QuickSort(int sort[], int low, int high){
	if (low < high){
		int pivotloc = Partition(sort, low, high);
		QuickSort(sort, low, pivotloc);
		QuickSort(sort, pivotloc + 1, high);
	}
}

/*选择排序:每一趟在n-i+1个记录中选取关键字最小的记录作为有序表序列的第i个记录。*/

void SelectSort(int sort[], int n){
	int k ,temp,min;
	for (int i = 1; i < n; ++i){
		min = sort[i];
		k = i;
		for (int j = i ; j <= n; ++j){
			if (sort[j] < min){
				k = j;
				min = sort[j];
			}
		}
		//if (i != k){
			temp = sort[i];
			sort[i] = sort[k];
			sort[k] = temp;
		//}
		
	}
}
/*堆排序*/
void HeapSort(int num[], int n);
void BuildHeap(int num[], int n);
void HeapAdjust(int num[], int s, int m);

/*归并排序：将两个或两个以上的有序表组合成一个新的有序表。*/
/*二路归并*/
void Merge(int sr[], int tr[], int i, int m, int n){

	int first = i;
	int j = m, k = i;
	while(i <= m && j <= n){
		if (sr[i] <= sr[j])
			tr[k++] = sr[i++];
		else
			tr[k++] = sr[j++];
	}
	printf("i = %d", i);
	printf("j = %d", j);
	printf("k = %d\n", k);
	while (i <= m)
		tr[k++] = sr[i++];
	while (j <= n)
		tr[k++] = sr[j++];
//	printf("k = %d\n", k);
	for (int l = 0; l < k; l++){
		sr[first + l] = tr[l];
	}
	

}
void mergesort(int sr[],int tr[] ,int first, int last){
	if (first == last){
		sr[first] = tr[first];
	}
	else if(first < last){
		int mid = (first + last) / 2  ;
		printf("%d\n", mid);
		mergesort(sr, tr, first, mid);
		mergesort(sr, tr, mid + 1, last);
		Merge(sr, tr, first, mid, last);
	}
}

/*基数排序*/
int getDigit(int x, int d);
void radixSort_one(int sort[], int begin, int end, int digit);
void radixSort(int sort[], int n);

int main(){
	int sort[11] = { 0,6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	int sort2[11] = { 0, 6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	int sort3[11] = { 0, 6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	insertion(sort, 10);
	for (int i = 1; i <= 10; i++){
		printf("%d ", sort[i]);
	}
	printf("\n");
	BinInsertSort(sort2, 10);
	for (int i = 1; i <= 10; i++){
		printf("%d ", sort2[i]);
	}
	printf("\n");
	int dlta[3] = { 4, 2, 1 };
	ShellSort(sort3, dlta, 3);
	for (int i = 1; i <= 10; i++){
		printf("%d ", sort3[i]);
	}
	printf("\n");

	int sort4[10] = { 6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	bubble_sort(sort4, 10);
	for (int i = 0; i < 10; i++){
		printf("%d ", sort4[i]);
	}
	printf("\n");
	int sort5[11] = { 0,6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	QuickSort(sort5, 1, 10);
	for (int i = 1; i <= 10; i++){
		printf("%d ", sort5[i]);
	}
	printf("\n");
	int sort6[11] = { 0, 6, 2, 7, 23, 12, 86, 33, 3, 70, 20 };
	SelectSort(sort6, 10);
	for (int i = 1; i <= 10; i++){
		printf("%d ", sort6[i]);
	}
	printf("\n");

	
	int sort7[14] = { 0,8, 5, 4, 6, 13, 7, 2, 9, 12, 11, 3, 10, 1 };
	HeapSort(sort7, 13);
	for (int i = 1; i <= 13; i++){
		printf("%d ", sort7[i]);
	}
	printf("\n mergesortn");

	int sort8[8] = { 4, 2, 5, 23, 66, 33, 1, 77 };
	int sort9[8] ;
	mergesort(sort8, sort9, 0, 7);
	for (int i = 0; i < 8 ; i++){
		printf("%d ", sort9[i]);
	}
	printf("\n");

	int sort10[10] = { 50, 123, 453, 187, 49, 30, 0, 3, 11, 100 };
	radixSort(sort10, 10);
	for (int i = 0; i < 10; i++){
		printf("%d ", sort10[i]);
	}
	printf("\n");

	return 0;
}

void BuildHeap(int num[], int n){
	int i;
	for (i = n / 2 - 1; i > 0; i--){
		HeapAdjust(num, i, n);
	}
}

void HeapAdjust(int num[], int s, int m){
	int rc = num[s];
	for (int j = 2 * s; j <= m; j++){
		if (j < m && num[j] < num[j + 1])
			++j;
		if (rc >= num[j])
			break;
		num[s] = num[j];
		s = j;
	}
	num[s] = rc;
}

void HeapSort(int num[],int n){
	BuildHeap(num, n);

	for (int i = n; i>1; --i){
		int temp = num[1];
		num[1] = num[i];
		num[i] = temp;
		HeapAdjust(num, 1, i - 1);
	}
}


/*桶排序*/
int getDigit(int x, int d){
	int a[] = { 1, 1, 10, 100 };
	return ((x / a[d]) % 10);
}
void radixSort_one(int sort[], int begin, int end, int digit){
	int radix = 10;
	int i = 0,j = 0;
	int count[10];//基数为10  // 存放各个桶的数据统计个数
	int bucket[10];//待排序的个数10
	for (int d = 1; d <= digit; d++){
		//置空各个桶的数据统计
		for (i = 0; i < radix; i++){
			count[i] = 0;
		}
		//统计各个桶将要装入的数据个数
		for (i = begin; i <= end; i++){
			j = getDigit(sort[i], d);
			count[j] ++;
		}
		//count[i]表示第i个桶的右边界索引
		for (i = 1; i < radix; i++){
			count[i] += count[i - 1];
		}
		//将数据依次装入桶中  从右向左，保证稳定性
		for (i = end; i >= begin; i--){
			j = getDigit(sort[i], d);//求出关键码的第k位的数字 576的第3为是5
			bucket[count[j] - 1] = sort[i];//放入对应的桶中，count[j]-1是第j个桶的右边界索引
			count[j]--;//对应桶的装入数据索引减一
		}

		for (i = begin, j = 0; i <= end; i++, j++){
			sort[i] = bucket[j];
		}

	}

}
void radixSort(int sort[], int n){
	radixSort_one(sort, 0, n - 1, 3);
}