jhrsya

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    //直接插入排序 
    void InsertSort(int A[], int n){	
    	int i,j;
    	for(i = 2; i <= n; i++){
    		if(A[i] < A[i - 1]){
    			A[0] = A[i];
    			for(j = i - 1; A[0] < A[j]; j--){
    				A[j + 1] = A[j];
    			}
    			A[j + 1] = A[0];
    		}
    	}
    }
    
    //折半排序 
    void divideSort(int A[], int n){
    	int i,j,low,high,mid;
    	for(i = 2; i <= n; i++){
    		if(A[i] < A[i - 1]){
    			A[0] = A[i];
    			low = 1;
    			high = i - 1;
    			while(low <= high){
    				mid = (low + high) / 2;
    				if(A[mid] < A[0])
    					low = mid + 1;
    				else
    					high = mid - 1;
    				
    			}
    			for(j = i - 1; j >= high + 1; j--)
    				A[j + 1] = A[j];
    			A[j + 1] = A[0];
    		}
    	} 
    }
    
    //希尔排序 
    void ShellSort(int A[], int n){
    	int i, j, dk;
    	for(dk = n / 2; dk >= 1; dk /= 2){	//步长从n/2逐渐减小到1 
    		for(i = dk + 1; i <= n; i+= dk){		//后续与直接插入排序差不多，只是步长1变为dk 
    			if(A[i] < A[i - dk]){
    				A[0] = A[i];
    				for(j = i - dk; j > 0 && A[j] > A[0]; j-= dk)
    					A[j + dk] = A[j];
    				A[j + dk] = A[0];
    			}
    		}
    	}
    }
    
    //冒泡排序 
    void bubbleSort(int A[], int n){
    	for(int i = 0; i < n - 1; i++){		//从0开始 
    		bool flag = false;		//判断是否发生过交换 
    		for(int j = n - 1; j > i; j--){
    			if(A[j] < A[j - 1]){
    				swap(A[j], A[j - 1]);
    				flag = true;
    			}
    		}
    		if(!flag) return;
    	}
    }
    
    //快速排序 
    int Partition(int A[], int low, int high){
    	int pivot = A[low];
    	while(low < high){
    		while(low < high && A[high] >= pivot) high--;
    		A[low] = A[high];
    		while(low < high && A[low] <= pivot) low++;
    		A[high] = A[low];
    	}
    	A[low] = pivot;
    	return low;
    }
    void quickSort(int A[], int low, int high){
    	if(low < high){
    		int pivotpos = Partition(A,low,high);
    		quickSort(A, low, pivotpos - 1);
    		quickSort(A, pivotpos+1, high);
    	} 
    }
    
    //简单选择排序 
    void selectSort(int A[], int n){
    	for(int i = 0; i < n - 1; i++){
    		int min = i;
    		for(int j = i + 1; j < n; j++){		//i+1....n-1找最小值所在位置 
    			if(A[j] < A[min]) min = j;
    		}
    		if(i != min) swap(A[min], A[i]);
    	}
    }
    
    //堆排序 
    void Adjust(int A[], int k, int n){		//一次调整，从K点到最下面的子树 
    	A[0] = A[k];
    	for(int i = 2 * k; i <= n; i++){		//沿着key较大的子结点向下筛选 
    		 if(i < n && A[i] < A[i + 1])		//选取Key较大的子结点 
    		 	i++;
    		if(A[0] > A[i]) break;
    		else{
    			A[k] = A[i];		//将A[i]调整到双亲结点上 
    			k = i;			//往下走 
    		}
    			  
    	}
    	A[k] = A[0];  		//被筛选的结点的值放入最终位置   
    	
    } 
    
    
    void BuildMaxHeap(int A[], int n){
    	for(int i = n / 2; i > 0; i--)	//从n / 2 至 1,反复调整堆
    		Adjust(A, i, n); 
    }
    void heapSort(int A[], int n){
    	BuildMaxHeap(A,n);
    	for(int i = n ; i > 1; i--){		//最后一个1无需交换,n - 1次的交换和建堆过程 
    		swap(A[i], A[1]);		//A[1]即最大值与堆底元素交换 
    		Adjust(A, 1, i - 1);		//整理，把剩余的i-1个元素整理成堆 
    	}
    } 
    
    //归并排序 
    void Merge(int A[], int low, int mid, int high){
    	int k,i,j;
    	int B[1000];
    	for(k = low; k <= high; k++)
    		B[k] = A[k];		//使用辅助数组B 
    	for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++){
    		if(B[i] <= B[j])		//把小的数字放在前面 
    			A[k] = B[i++];		 
    		else
    			A[k] = B[j++]; 
    	}
    	//哪边还剩下，就把那边 的元素放在A数组之后 
    	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 A[100], n;
    	cin >> n;
    	for(int i = 1; i <= n; i++){
    		cin >> A[i];
    	}
    	MergeSort(A,1, n);
    	for(int i = 1; i <= n; i++)
    		cout << A[i] << " ";
    //	for(int i = 0; i < n; i++)
    //		cin >> A[i];
    //	selectSort(A,n); 
    //	for(int i = 0; i < n; i++)
    //		cout << A[i] << " "; 
    }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jhrsya

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

【计算球体积】（C语言代码）

考研排序算法（快速排序，归并排序，堆排序）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

关于float，double变量的几点说明

1050题解（结构体数组与结构体指针的使用）

理财计划（C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

纪念品分组（C语言代码）

WU-C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

数字统计（C语言代码）

jhrsya

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （Java代码）

A+B for Input-Output Practice (VII) （C++代码）

【计算球体积】 （C语言代码）

考研排序算法（快速排序，归并排序，堆排序）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

关于float，double变量的几点说明

1050题解（结构体数组与结构体指针的使用）

理财计划 （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

纪念品分组 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

数字统计 （C语言代码）

【计算球体积】（C语言代码）

　　评论区

理财计划（C语言代码）

纪念品分组（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

数字统计（C语言代码）