数据结构与算法(c++)--排序算法

àì夳堔傛蜴生んèń 2022-12-05 12:27 153阅读 0赞

## 数据结构与算法(c++)–排序算法 ##

这篇文章主要简单记录下数据结构与算法中的排序算法技术

**书签**

*  插入排序
    
     *  直接插入排序
     *  希尔排序
 *  交换排序
    
     *  起泡排序
     *  快速排序
 *  选择排序
    
     *  简单选择排序
     *  堆排序
 *  归并排序
    
     *  二路归并排序
 *  分配排序
    
     *  桶式排序
 *  各排序的时空性能

### 插入排序 ###

##### 直接插入排序 #####

**基本思想：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都安排好序。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center]

直接插入排序代码：

void Insertsort(int data[],int length){
        //直接插入排序
    	int i,j,temp;
    	for (i=1;i<length;i++){
         //排序进行length-1次
    		temp=data[i];   //获取待插元素
    		for(j=i-1;j>=0&&temp<data[j];j--){
         //寻找插入位置
    			data[j+1]=data[j];
    		}
    		data[j+1]=temp;
    	}
    }

##### 希尔排序 #####

**基本思想：先将整个待排序记录序列分割成若干个子序列，待整个序列基本有序时，再对全体记录进行一次直接插入排序。**

希尔排序代码：

void Shellsort(int data[],int length){
        //希尔排序
    	int d,i,j,temp;
    	for (d=length/2;d>=1;d=d/2){
        //获取增量d，然后再进行这届插入排序
    		for (i=d;i<length;i++){
        
    			temp=data[i];   //获取待插元素
    			for(j=i-d;j>=0&&temp<data[j];j=j-d)
    				data[j+d]=data[j];
    			data[j+d]=temp;
    		}
    	}
    }

### 交换排序 ###

##### 起泡排序 #####

**基本思想：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]

起泡排序代码：

void Bubblesort(int data[],int length){
        //起泡排序
    	int j,exchange,bound,temp;
    	exchange=length-1;//第一趟起泡排序的区间是[0~length-1]
    	while(exchange!=0){
        
    		bound=exchange;
    		exchange=0;
    		for(j=0;j<bound;j++){
        
    			if(data[j]>data[j+1]){
        
    				temp=data[j];
    				data[j]=data[j+1];
    				data[j+1]=temp;
    				exchange=j;
    			}
    		}
    	}
    }

##### 快速排序 #####

**基本思想：首先选定一个轴值，将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]

快速排序代码：

int Partition(int data[],int first,int last){
        //快速排序1
    	int i=first,j=last,temp;
    	while(i<j){
        
    		while(i<j&&data[i]<=data[j])
    			j--;
    		if(i<j){
        
    			temp=data[i];
    			data[i]=data[j];
    			data[j]=temp;
    			i++;
    		}
    		while(i<j&&data[i]<=data[j])
    			i++;
    		if(i<j){
        
    			temp=data[i];
    			data[i]=data[j];
    			data[j]=temp;
    			j--;
    		}
    	}
    	return i;
    }
    
    void Quicksort(int data[],int first,int last){
        //快速排序2
    	if(first<last){
        
    		int pivot = Partition(data,first,last);  //一次划分
    		Quicksort(data,first,pivot-1);  //对左侧子序列进行快速排序
    		Quicksort(data,pivot+1,last);   //对右侧子序列进行快速排序
    	}
    }

### 选择排序 ###

##### 简单选择排序 #####

**基本思想：第i趟排序在待排序列中 ri ~ rn(1 ≤ i ≤ n-1)中选取最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 3]

简单选择排序代码

void Selectsort(int data[],int length){
        //简单选择排序
    	int i,j,index,temp;
    	for(i=0;i<length-1;i++){
        
    		index=i;
    		for(j=i+1;j<length;j++)//在无序区获取最小的序列
    			if(data[j]<data[index]) index=j;
    		if(index!=i){
        
    			temp=data[i];
    			data[i]=data[index];
    			data[index]=temp;
    		}
    	}
    }

##### 堆排序 #####

**基本思想：首先将待排序序列调整成一个堆，此时，选出了堆中所有记录的最大者即堆顶元素，然后将堆顶记录移走，并将剩余记录再调整成堆，这样又找出次大记录，以此类推，直到堆中只有一个记录。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 4]

堆排序代码

void Sift(int data[],int k,int last){
        //堆排序1
    	int i=k;
    	int j=2*i+1;
    	int temp;
    	while(j<=last){
        
    		if(j<last && data[j]<data[j+1]) j++;
    		if(data[i]>data[j]) break;
    		else{
        
    			temp=data[i];
    			data[i]=data[j];
    			data[j]=temp;
    			i=j;
    			j=2*i+1;
    		}
    	}
    }
    
    void Heapsort(int data[],int length){
        //堆排序2
    	int i,temp;
    	for(i=ceil(length/2)-1;i>=0;i--){
        
    		Sift(data,i,length-1);
    	}
    	for(i=1;i<length;i++){
        
    		temp=data[0];
    		data[0]=data[length-i];
    		data[length-i]=temp;
    		Sift(data,0,length-i-1); //重建堆
    	}
    }

### 归并排序 ###

##### 二路归并排序 #####

**基本思想：将待排序序列\{r1, r2, …,rn\}划分为两个长度相等的子序列\{r1, r2, …,rn/2\}和\{rn/2+1, rn/2+2, …,rn\}，分别对这两个子序列进行排序，得到两个有序子序列，再将这两个有效子序列合并成一个有效子序列。**

二路归并排序代码

void Merge(int data[],int first1,int last1,int last2,int length){
        //二路归并排序1
    
    	int *temp=new int [length+1];//申请辅助空间
    	int i=first1;
    	int j=last1+1;
    	int k=first1;
    	while(i<=last1&&j<=last2){
        
    		if(data[i]<=data[j]) temp[k++]=data[i++];
    		else temp[k++]=data[j++];
    	}
    	while(i<=last1) temp[k++]=data[i++];
    	while(j<=last2) temp[k++]=data[j++];
    	for(i=first1;i<=last2;i++) data[i]=temp[i];//辅助空间数据传回数组
    	delete[] temp;
    }
    
    void Mergesort(int data[],int first,int last,int length){
        //二路归并排序2
    	if(first==last) return;//子序列中只有一个记录
    	else{
        
    		int mid=(first+last)/2;
    		Mergesort(data,first,mid,length);//归并排序左半子序列
    		Mergesort(data,mid+1,last,length);//归并排序右半子序列
    		Merge(data,first,mid,last,length);//合并已排序的子序列
    	}
    }

### 分配排序 ###

##### 桶式排序 #####

**基本思想：获取待排序序列中的最大值m，设置m+1个桶，将数值为i的记录分配到第i个桶中，其余无数值的桶为空桶，然后再将各个桶中的记录（忽略空桶）依次取出。**

桶式排序代码

int Findmax(int data[],int length){
        //桶式排序1
    	int i,max;
    	max=data[0];
    	for(i=1;i<length;i++){
        
    		if(data[i]>max)
    			max=data[i];
    	}
    	return max; //获取最大值来创建桶数组
    }
    
    void Bucketsort(int data[],int length){
        //桶式排序2
    	int i,m;
    	m=Findmax(data,length);
    	int *count=new int[m+1];    //创建桶数组
    	for(i=0;i<=m;i++)           //桶数组全部数值赋予0
    		count[i]=0;
    	for(i=0;i<length;i++)       //待排序列的数值对应的桶数组下标，并其数值赋予1
    		count[data[i]]++;
    	for(i=0;i<=m;i++){
                  //取出
    		while(count[i]>0){
        
    			cout<<i<<" , ";
    			count[i]--;
    		}
    	}
    }

### 各排序的时空性能 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 5]

END！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/72b8d1d2741249808a5fe19eb05003e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/10e4db6eca504356ab84d47591fd08f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/ae45cddaf346459f8b332b54ccdbc2ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/8ab3456dfab940149856d531b51dc296.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/a2a55edaa9664e4a8127260e0ecdea4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Njc5MTk0Mg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/76d86a8b268942a993273187706d6ed3.png