几种排序算法的实现

ゝ一纸荒年。 2023-06-11 12:21 15阅读 0赞

## 插入排序 ##

*  **直接插入排序**

//对数组int A[n]进行直接插入排序
    void InsertSort(int A,int n){
        
    	int j,temp;
    	for(int i=1;i<n;i++){
        
    		temp=A[i];//将当前待排序的元素存储在temp中
    		j=i-1;//从当前待排元素的前一个元素开始扫描数组
    		while(j>=0&&A[j]>temp){
        
    			A[j+1]=A[j];
    			j--;
    		}
    		R[j+1]=temp;//完成下标为i的元素的排序
    	}
    }

*  **折半插入排序**

//对数组A[n]进行折半插入排序
    void InsertSort(int A[],int n){
        
    	int temp,low,high,mid
    	for(int i=1;i<n;i++){
        
    		temp=A[i];//将当前待排序元素存储到temp中
    		low=0;high=i-1;
    		while(low<=high){
        //通过折半查找，找到待排序元素应该插入的位置为high+1;
    			mid=(low+high)/2;
    			if(A[mid]>temp) low=mid+1;
    			else high=mid-1;
    		}//折半查找结束
    		//移动元素
    		for(j=i;j>high+1;j--){
        
    			A[j]=A[j-1];
    		}
    		A[j]=temp;//将下标为i的元素排好序
    	}
    }

## 交换排序 ##

*  **冒泡排序**

//对数组A[n]进行冒泡排序
    void BubbleSort(int A[],int n){
        
    	bool flag;
    	for(int i=0;i<n-1;i++){
        //n个元素最多进行n-1趟排序
    		flag=false;
    		for(int j=0;j<n-i-1;j++){
        
    			if(A[j]>A[j+1]){
        
    				swap(A[j],A[j+1]);//按照从大到小的顺序排列
    				flag=true;
    			}
    		}
    		if(flag==false) return;//如果某一趟冒泡结束，未发生交换，说明数组中的元素已经实现有序排列
    	}
    }

*  **快速排序**
 *  在待排序的列表中选择一个元素作为基准pivot，通过一趟排序将待排序表划分为两部分，一部分元素小于pivot,另一部分元素大于pivot,此时pivot放在了其最终位置上。而后递归的对其子表重复上述过程

void QuickSort(int R[],int low,int high){
        
    	int pivot,i,j;
    	i=low;j=high;
    	if(low<high){
        
    		pivot=R[low];
    		while(i!=j){
        
    			while(j>i&&R[j]>pivot;j--)//从右向左
    			if(j>i){
        
    				R[i]=R[j];
    				i++;
    			}
    			while(i<j&&R[i]<pivot;i++)//从左向右
    			if(i<j){
        
    				R[j]=R[i];
    				j--;
    			}
    		}//当i=j,循环结束
    		R[i]=pivot;//pivot最终位置确定
    		QuickSort(R,low,i-1);
    		QuickSort(R,i+1;high);
    	}
    }

## 选择排序 ##

*  **简单选择排序**
 *  每一趟排序，找到待排序列中的最小元素，与该代派序列的第一个元素交换位置

void SeleteSort(int A[],int n){
        
    	int i;j;k;
    	for(i=0;i<n;i++){
        
    		k=i;
    		for(j=i+1;j<n;j++){
         //寻找带排序列最小元素的下标
    			if(A[j]<A[k])
    				k=j;
    		}
    		swap(A[k],A[i]);
    	}
    }

*  **设有一个数组为a1,a2…an，现要求将an放在排序后正确的位置上，实现该算法**

//使用快速排序，将an作为枢轴量
    void Sort(int A[],int low,int high){
        
    	int i=low,j=high;
    	int pivot;
    	if(i>=j) return;
    	while(i!=j){
        
    		pivot=A[j];
    		while(i<j&&A[i]<pivot)
    			i++;
    		if(i<j){
        
    			A[j]=A[i];
    			j--;
    		}
    		while(i<j&&A[j]>pivot)
    			j--;
    		if(i<j){
        
    			A[i]=A[j];
    			i++;
    		}
    	}
    	A[i]=pivot;
    }

*  **输入一个整数数组，调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分**
 *  奇数和奇数、偶数和偶数之间的相对位置可变

//使用快速排序
    void Sort(int A[],int low,int high){
        
    	int i=low,j=high;
    	int pivot;
    	if(i>=j) return;
    	while(i!=j){
        
    		pivot=A[i];
    		while(i<j&&A[j]%2==0)
    			j--;
    		if(i<j){
        
    			A[i]=A[j];
    			i++;
    		}
    		while(i<j&&A[i]%2==1)
    			i++;
    		if(i<j){
        
    			A[j]=A[i];
    			j--;
    		}
    	}//while
    	A[i]=pivot;
    }

*  奇数奇数、偶数偶数之间的相对位置不可变

//方法一：使用冒泡排序
    void Sort(int A[],int n){
        
    	//如果是前偶后奇则交换位置
    	bool flag;
    	for(int i=0;i<n-1;i++){
        
    		for(int j=0;j<n-1-1;j++){
        
    			if(A[j]%2==0&&A[j+1]%2==1){
        
    				temp=A[j];
    				A[j]=A[j+1];
    				A[j+1]=temp;
    				flag=true;
    			}
    		}//for
    		if(flag==false) return;
    	}//for
    }
    
    //方法二：创建辅助数组
    void Sort(int A[],int n){
        
    	int a[n],int b[n];
    	int j=0,k=0;
    	for(int i=0,i<n;i++){
        
    		if(A[i]%2==0){
        
    			a[j++]=A[i];
    		}else{
        
    			b[k++]=A[i];
    		}
    	}
    	int t=0;
    	for(;j<n;j++){
        
    		a[j]=b[t];
    		t++;
    	}
    }

*  **带头结点的双向链表，对其进行双向起泡法升序排列**

bool doublebubbleSort(DLinkList &L){
        
    	DLinkList *p,*q=NULL;
    	bool flag=true;
    	while(flag==true){
        
    		p=L->next;
    		flag=false;
    		while(p->next!=q){
        
    			if(p->data>p->next->data){
        
    				swap(p->data,p->next-data);
    				flag=true;
    			}
    			p=p->next;
    		}//while
    		q=p;
    		p=q->prior;
    		while(p->prior!=L){
        
    			if(p->data<p->prior->data){
        
    				swqp(p->data,p->prior->data);
    				flag=true;
    			}
    			p=p->prior;
    		}//while
    		L=p;//下次起泡的起点
    	}
    }