《MY数据结构与算法》----八大排序算法（含优化与算法拓展）

素颜马尾好姑娘i 2022-05-18 11:00 146阅读 0赞

# 一：八大排序算法比较 #

![20150821162219212][]

# 二：八大排序算法代码实现，以及优化与拓展 #

冒泡排序：优化为增加哨兵。  
选择排序：  
希尔排序：  
插入排序：  
归并排序：拓展为应用在求逆序对  
快速排序：拓展为求数组中第n大的值。  
堆排序：    拓展为求数组中前n个大的值。  
归并排序，快速排序，堆排序，的优化方法之一都可以在数组元素个数小于15的时候用插入排序。（代码未添加）  
快速排序：可优化为当重复的元素过多的时候选择3路归并（代码未添加）  
快速排序：变形可变为不使用递归，而使用栈和队列的方式（代码未添加）  
具体我在此博客看到有介绍。可作参考：[https://blog.csdn.net/Vichyssoise/article/details/78922138][https_blog.csdn.net_Vichyssoise_article_details_78922138]

#include <iostream>
    #include <stdlib.h>
    
    #define ARR_MAX_COUNT 10
    #define p() cout << "-----------------------------\n";
    #define __PRINT_FUNC() cout << __func__ << endl;
    
    using namespace std;
    
    class TEST_SORT_ARR {
    
    private :
    	int arr[ARR_MAX_COUNT];
    	int inversion_num;
    
    public  :
    	TEST_SORT_ARR() ;
    	~TEST_SORT_ARR() ; 
    	void prn();
    
    	void bubbling_sort();
    	void bubbling_sort_add_sentry_optimize();
    	void select_sort();
    	void insert_sort();
    	void shell_sort();
    	void merge_sort();
    	int  merge_sort_app_get_inversion();
    	void quick_sort();
    	int  quick_sort_app_return_value_of_nox(int id);
    	void heap_sort();
    
    private :
    	void __shellInsertSort(int arr[] , int n , int dk);
    	void __merge_sort(int arr[] , int l , int r);
    	void __merge(int arr[] , int l , int middle ,int  r) ;
    	void __merge_sort_app_inversion_num(int arr[] , int l , int r);
    	void __merge_app_inversion_num(int arr[] , int l , int middle ,int  r) ;
    	void __quick_sort(int arr[] , int l , int r);
    	int  __quick(int arr[] , int l ,int r);
    	void __heap_sort(int arr[] , int count);
    	int  __parent(int n);
    	int  __leftchild(int n);
    	int  __rightchild(int n);
    	void __shift_down(int arr[] , int len , int i);
    };
    
    int TEST_SORT_ARR::__parent(int n) {
    	return (n-1)/2;
    }
    int TEST_SORT_ARR::__leftchild(int n) {
    	return 2*n+1;
    }
    int TEST_SORT_ARR::__rightchild(int n) {
    	return 2*n+2;
    }
    
    void TEST_SORT_ARR::__shift_down(int arr[] , int len , int i) {
    	int lchild = __leftchild(i);
    	int rchild = __rightchild(i);
    	int nmax;
    	
    	if( lchild <  len && arr[lchild] > arr[i] )	
    		nmax = lchild;	
    	else 
    		nmax = i;
    	
    	if( rchild < len && arr[rchild] > arr[nmax] )
    		nmax = rchild;
    
    	if( nmax != i)
    	{
    		swap(arr[i] , arr[nmax]);
    		__shift_down(arr, len, nmax);
    	}
    }
    
    void TEST_SORT_ARR::__heap_sort(int arr[] , int n) {
    	for(int i = __parent(n-1) ; i>=0 ; i--)
    	{
    		__shift_down(arr,n,i);
    	
    	}
    	for(int i = n-1 ; i>0 ; i-- ) {
    		swap(arr[0] , arr[i] );
    		n--;
    		__shift_down(arr,n,0);
    	}
    }
    
    void TEST_SORT_ARR::heap_sort() {
    __PRINT_FUNC();
    	__heap_sort(arr,ARR_MAX_COUNT);
    }
    
    
    int TEST_SORT_ARR::quick_sort_app_return_value_of_nox(int id) {
    __PRINT_FUNC();
    	int middle = __quick(arr, 0 , ARR_MAX_COUNT-1);
    	while( middle != id) {
    		if( middle>id) {
    			middle = __quick(arr,0,middle-1);
    		}
    		else {
    			middle = __quick(arr,middle+1,ARR_MAX_COUNT-1);
    		}
    	}
    	return arr[middle];
    }
    
    int TEST_SORT_ARR::__quick(int arr[] , int l , int r) {
    	if( l>=r )
    		return l;
    	swap(arr[l] , arr[ rand()%(r-l+1)+l ]);
    
    	int v = arr[l];
    
    	int i = l+1;
    	int j = r;
    	while( true ) {
    		while( i<=r && arr[i]<= v) {
    			i++;
    		}
    		while( j>=l+1 && arr[j]>= v) {
    			j--;
    		}
    		if( i>=j)
    			break;
    		swap(arr[i] , arr[j]);
    		i++;
    		j--;
    		
    
    	}
    	swap(arr[j] , arr[l]);
    	return j;
    }
    
    
    void TEST_SORT_ARR::__quick_sort(int arr[] , int l , int r) {
    	if( l>=r )
    		return ;
    	int middle = __quick(arr, l , r);
    	__quick_sort(arr,l,middle-1);
    	__quick_sort(arr,middle+1 , r);
    }
    
    void TEST_SORT_ARR::quick_sort() {
    __PRINT_FUNC();
    	__quick_sort(arr,0,ARR_MAX_COUNT-1);
    }
    
    
    
    
    
    
    void TEST_SORT_ARR::__merge_app_inversion_num(int arr[] , int l , int middle ,int  r) {
    	int tempArr[r-l+1] ;
    	for( int i=l ; i<=r ; i++){
    		tempArr[i-l] = arr[i];	
    	}
    	
    	int lp = l,lr=middle+1;
    	for( int i=l ; i<=r ; i++) {
    		if( lp > middle ) {
    			arr[i] = tempArr[lr-l];
    			lr++;
    		}
    		else if( lr > r ) {
    			arr[i] = tempArr[lp-l];
    			lp++;
    		}
    		else if( tempArr[lr-l] <= tempArr[lp-l] ) {
    			arr[i] = tempArr[lr-l];	
    			inversion_num += (middle-lp+1);
    			lr++;
    		}
    		else {
    			arr[i] = tempArr[lp-l];
    			lp++;
    		}
    	}	
    }
    
    void TEST_SORT_ARR::__merge_sort_app_inversion_num(int arr[] , int l , int  r) {
    	if( l>=r)
    		return ;
    	int middle = (r-l)/2+l;
    	__merge_sort_app_inversion_num(arr,l,middle);
    	__merge_sort_app_inversion_num(arr,middle+1,r);
    	__merge_app_inversion_num(arr,l,middle,r);	
    }
    
    int  TEST_SORT_ARR::merge_sort_app_get_inversion() {
    __PRINT_FUNC();
    	inversion_num = 0;
    	__merge_sort_app_inversion_num(arr,0,ARR_MAX_COUNT-1);
    	return inversion_num;
    }
    
    void TEST_SORT_ARR::__merge(int arr[] , int l , int middle ,int  r) {
    	int tempArr[r-l+1] ;
    	for( int i=l ; i<=r ; i++){
    		tempArr[i-l] = arr[i];	
    	}
    	
    	int lp = l,lr=middle+1;
    	for( int i=l ; i<=r ; i++) {
    		if( lp > middle ) {
    			arr[i] = tempArr[lr-l];
    			lr++;
    		}
    		else if( lr > r ) {
    			arr[i] = tempArr[lp-l];
    			lp++;
    		}
    		else if( tempArr[lr-l] < tempArr[lp-l] ) {
    			arr[i] = tempArr[lr-l];	
    			lr++;
    		}
    		else {
    			arr[i] = tempArr[lp-l];
    			lp++;
    		}
    	}	
    }
    
    void TEST_SORT_ARR::__merge_sort(int arr[] , int l , int  r) {
    	if( l>=r)
    		return ;
    	int middle = (r-l)/2+l;
    	__merge_sort(arr,l,middle);
    	__merge_sort(arr,middle+1,r);
    	__merge(arr,l,middle,r);	
    }
    
    
    void TEST_SORT_ARR::merge_sort() {
    __PRINT_FUNC();
    	__merge_sort(arr,0,ARR_MAX_COUNT-1);
    }
    
    
    
    void TEST_SORT_ARR::__shellInsertSort(int arr[] , int n , int dk) {
    	for(int i=dk ; i<ARR_MAX_COUNT ; i+=dk) {
    		int flag = i-dk;
    		int val = arr[i];
    		while( (flag>=0)&&(arr[flag]>val))
    		{
    			arr[flag+dk] = arr[flag];
    			flag -= dk;	
    		}
    		arr[flag+dk] = val;
    	}
    }
    
    void TEST_SORT_ARR::shell_sort() {
    __PRINT_FUNC();
    	int dk = ARR_MAX_COUNT/2;
    	while(dk>=1) {
    		__shellInsertSort(arr,ARR_MAX_COUNT,dk);
    		dk /= 2;
    	}
    }
    
    
    
    void TEST_SORT_ARR::insert_sort() {
    __PRINT_FUNC();
    	for(int i=1; i<ARR_MAX_COUNT ; i++) {
    		int flag = i-1;
    		int val = arr[i];
    		// ba dangqianzhi tichulai baocunwei val;
    		// ranhou qianmian de meigezhi he val bijiao , bitada,jiu wanghou yidong 
    		while((flag>=0) && (arr[flag]>val))
    		{
    			arr[flag+1] = arr[flag];
    			flag--;
    		}
    		//zuihou zai jiang val fuzhi guoqu ;
    		arr[flag+1] = val;
    	}
    
    }
    
    void TEST_SORT_ARR::select_sort() {
    __PRINT_FUNC();
    	for(int i=0 ; i<ARR_MAX_COUNT-1 ; i++) {
    		for(int j=i+1 ; j<ARR_MAX_COUNT ; j++)
    		{
    			if(arr[i] > arr[j])
    				swap(arr[i],arr[j]);
    		}
    	}
    }
    
    void TEST_SORT_ARR::prn() {
    	for(int i=0 ; i<ARR_MAX_COUNT ; i++)
    		cout << arr[i] << " ";
    	cout << endl;
    }
    
    TEST_SORT_ARR::TEST_SORT_ARR() {
    	for(int i=0 ; i<ARR_MAX_COUNT ; i++) {
    		arr[i] = rand()%88;
    	}
    }
    TEST_SORT_ARR::~TEST_SORT_ARR() {}
    
    
    
    void TEST_SORT_ARR::bubbling_sort(){
    	for(int i=0 ; i<ARR_MAX_COUNT-1; i++) {
    		for(int j=0 ; j<ARR_MAX_COUNT-1-i ; j++) {
    			if(arr[j] > arr[j+1])
    				swap(arr[j],arr[j+1]);
    		}
    	}
    }
    
    void TEST_SORT_ARR::bubbling_sort_add_sentry_optimize(){
    	int flag = 0;
    	for(int i=0 ; i<ARR_MAX_COUNT-1; i++) {
    		for(int j=0 ; j<ARR_MAX_COUNT-1-i ; j++) {
    			if(arr[j] > arr[j+1]) {
    				swap(arr[j],arr[j+1]);
    				flag = 1;
    			}
    		}
    		if( 1==flag ) {
    			flag = 0;
    		}
    		else {
    			return ;
    		}
    	}
    }
    
    
    int main() 
    {
    	TEST_SORT_ARR  d;
    	d.prn();
    	d.merge_sort();
    	d.prn();
    	p();
    
    	TEST_SORT_ARR  h;
    	h.prn();
    	h.heap_sort();
    	h.prn();
    	p();
    
    	TEST_SORT_ARR  f;
    	f.prn();
    	f.quick_sort();
    	f.prn();
    	p();
    
    	
    	TEST_SORT_ARR  g;
    	p();
    	g.prn();
    	cout << "no.3 is :" << g.quick_sort_app_return_value_of_nox(3) << endl;
    	g.prn();
    	p();
    	
    	TEST_SORT_ARR  e;
    	e.prn();
    	cout << "ni xu dui num : " << e.merge_sort_app_get_inversion() <<endl;
    	e.prn();
    	p();
    
    	TEST_SORT_ARR  a;
    	a.prn();
    	a.bubbling_sort();
    	a.prn();
    	p();
    	
    	TEST_SORT_ARR  c;
    	c.prn();
    	c.shell_sort();
    	c.prn();
    	p();
    
    	TEST_SORT_ARR  b;
    	b.prn();
    	b.insert_sort();
    	b.prn();
    	p();
    	
    	TEST_SORT_ARR  aa;
    	aa.prn();
    	aa.bubbling_sort_add_sentry_optimize();
    	aa.prn();
    	p();
    
    
    	TEST_SORT_ARR  ab;
    	ab.prn();
    	ab.select_sort();
    	ab.prn();
    	p();
    }

[20150821162219212]: /images/20220518/069ab1dcd7be481fabbc91eeadb88b73.png
[https_blog.csdn.net_Vichyssoise_article_details_78922138]: https://blog.csdn.net/Vichyssoise/article/details/78922138