博客

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

//一下排序方法默认从小到大，数组从0开始

/**
 * 直接插入排序：边比较边移动位置
 *  
 * */

void directSort(int *a, int length){
	int i,j; 
	for(i = 1; i < length;i++){//i 从1开始知道数组结尾
		if(a[i-1] > a[i]){
			//开始寻找位置
			int tmp = a[i];
			for(j=i-1; j >= 0;j--){
				if(a[j] > tmp){
					a[j+1] = a[j];//向后移动位置
				}else{
					break;
				}
			}
			a[j+1] = tmp;//赋值
		}
	}
}

/**
 * 折半插入排序：先找位置在移动元素
 * 
 * 
 * */
void binarySort(int *a, int length){
	int i,low,height,mid;
	for(i = 1; i < length ;i++){//和直接插入排序一样从1开始
		//寻找需要插入的位置
		int tmp = a[i];
		low = 0; height = i-1;
		while (low <= height){
			mid = (low + height)/2;
			if(a[mid] < tmp){
				low = mid+1;
			}else{
				height = mid -1;
			}
		}
		//移动height后面的元素
		for(int j = i-1; j >= height; j--){
			a[j+1] = a[j];
		}
		a[height+1] = tmp;//赋值
	}
}


/**
 * 希尔排序：先基本有序在整体有序
 * 根据步长来排
 * 
 * */
void shellSort(int *a, int length){
	int dk,i,j;//dk步长，i 比较时用，j 寻找插入位置时用 
	for(int dk = length/2; dk > 0; dk /= 2){ //步长从length/2 到 1
		for(i = dk ;i < length; i++){ //i 从第二个分组到最后
			if(a[i] < a[i-dk]){
				int tmp = a[i];//tmp是哨兵
				for(j = i-dk; j >= 0 && tmp < a[j];j -= dk){
					a[j+dk] = a[j];
				}
				a[j+dk] = tmp;
			}
			
		}
		// printf("dk = %d,i = %d \n",dk,i);
		// for (int k = 0; k < length ; k++){
		// 	printf("%d ", a[k]);
		// }
		// printf("\n");
	}
}

/**
 * 冒泡排序：一层一层的向外冒
 * 
 * */
void bubbleSort(int *a, int length){
	bool flag = false;
	//每次循环都找出最小的一个放在第i位
	for(int i = 0 ;i < length; i++){
		//循环比较找出最小的一个来
		for(int j = length-1;j >i ;j--){
			if(a[j] < a[j-1]){
				int tmp = a[j];a[j] = a[j-1];a[j-1] =tmp;
				flag =true;
			}
		}
		// for (int k = 0; k < length ; k++){
		// 	printf("%d ", a[k]);
		// }
		// printf("\n");
		if(!flag){
			return;
		}
		
	}
}

/**
 * 快速排序：每次选一个数作为基准，每进行一次划分就会将基准放到它最终的位置
 * 
 * */
//进行划分
int partition(int *a,int low, int height){
	//存放基准
	int tmp = a[low];
	//寻找tmp的最终位置，直到low == height时结束
	while(low < height){
		//从height往后找，找到一个比基准小的数据
		while (low < height && tmp <= a[height]){
			height--;
		}
		a[low] =a[height];
		//从low往前找找到一个比基准大的数据
		while (low < height && tmp >= a[low]){
			low++;
		}
		a[height] = a[low];
	}
	a[low] = tmp;
	return low;
}
//定义一个递归
void quickSort(int *a,int low, int height){
	if(low < height){
		int i = partition(a,low,height);
		//利用了二叉查找的思想
		quickSort(a,low,i-1);
		quickSort(a,i+1,height);
	}
}

/**
 * 简单选择排序：每次选一个最小的元素放在第i个位置
 * 
 * */
void selectSort(int *a, int length){
	//遍历整个数组除了最后一位
	for(int i = 0;i < length - 1; i++){
		int min = i;
		for(int j = i+1;j < length ; j++){//寻找最小的位置
			if(a[min] > a[j]){
				min = j;
			}
		}
		//交换
		if(min != i){
			int tmp = a[min];
			a[min] = a[i];
			a[i] = tmp;			
		}
	}
}
/**
 * 堆排序：利用大根堆或者小根堆的性质
 * 数组下标从0开始，这里传入的值是数组的长度
 * */

//这个方法是重点
void headAndJust(int *a,int k ,int length){
	//暂存根节点
	int tmp = a[k];
	//i为k 的左孩子，每次循环之后k都是根、左、右中最大的节点
	for(int i = 2*k+1;i < length;i = i*2+1){
		//选取孩子较大的节点，若右孩子比较大，则令i++
		if(i  < length-1 && a[i] < a[i+1]){
			i++;
		}
		if(tmp >= a[i]){//左孩子大于右孩子，但是小于根节点
			break;
		}else{//左孩子大于右孩子，且大于根
			a[k] = a[i];//将a[i]调整到双亲节点上
			k = i;
		}
	}
	//将根节点放到相应的位置上
	a[k] = tmp;
}

//初始化堆
void buildMaxHeap(int *a,int length){
	//从最后一个分支节点开始向前遍历
	for(int i = length/2;i >= 0;i--)
		headAndJust(a,i,length);

	for (int t = 0; t < length; t++)
	{
		printf("%d ", a[t]);
	}
	printf("\n");
}

//堆排序
void heapSort(int *a,int length){
	buildMaxHeap(a,length);
	for(int i = length-1;i > 0 ; i--){
		//没有排好序的交换第一个元素和最后一个元素
		int tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		//进行堆的调整由0到i
		headAndJust(a,0,i);
	}
}

/**
 * 归并排序：将两个有序的序列合并为一个有序队列
 * 二路归并排序用于内部排序，多路归并排序用于外部排序
 * 
 * 重点是merge()
 * */

void merge(int *a,int low,int mid, int high){
	int i ,j,k;
	//需要一个辅助空间，暂时存贮需要合并的两个子序列
	int *b = (int*)malloc(sizeof(a));
	//将需要排序的两个子序列复制到b
	for(int i = low;i <= high;i++){
		b[i] = a[i]; 
	}
	//循环比较两个子序列，插入到a中，直到有一个子序列为空
	for(i = low,j = mid+1,k = i; i <= mid && j <= high;k++){
		if(b[i] <= b[j]){
			a[k] = b[i];
			i++;
		}else{
			a[k] = b[j];
			j++;
		}
	}
	//若有一个子序列还没有完则直接加到末尾
	while (i <= mid){
		a[k++] = b[i++];
	}
	while (j <= high){
		a[k++] = b[j++];
	}

}

void mergeSort(int *a, int low,int high){
	if(low < high){
		int mid = (low + high)/2;
		mergeSort(a,low,mid);//排做半个的
		mergeSort(a,mid+1,high);//排有半个的
		merge(a,low,mid,high);//归并
	}

}


int main(){
	int t;
	// int array[] = {50, 26, 38, 80, 70, 90, 8, 30, 40, 20};

	int array[] = {53, 17, 78, 9, 45, 65, 87, 32};
	// heapSort(array , sizeof(array) / sizeof(array[0]));

	mergeSort(array , 0 ,(sizeof(array) / sizeof(array[0]))-1);

	for (t = 0; t < sizeof(array) / sizeof(array[0]); t++)
	{
		printf("%d ", array[t]);
	}
	printf("\n");
	return 0;
}