数据结构之排序

￡神魔★判官ぃ 2022-05-28 07:51 158阅读 0赞

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    //插入排序
    void InsertSort(int data[],int n)
    {
        int i,j;
        int temp;
        for(i=1;i<n;i++){
            if(data[i]<data[i-1]){
                temp=data[i];
                for(j=i-1;j>=0&&data[j]>temp;j--){
                    data[j+1]=data[j];
                }
                data[j+1]=temp;
            }
        }
    }
    
    //选择排序
    
    void SelectSort(int data[],int n)
    {
        int i,j,k,temp;
        for(i=0;i<n-1;i++)
        {
            k=i;
            for(j=i+1;j<n;j++){
                if(data[j]<data[k]){
                    temp=data[j];
                    data[j]=data[k];
                    data[k]=temp;
                } 
            }
        }
    }
    //希尔排序
    void ShellSort(int data[], int n)
    {
        int i,j,k,temp;
        temp=n;
        temp/=2;
        while(temp>0){
            for(k=temp;k<n;k++)
    		{
    			if(data[k-temp]>data[k])
    			{
    				i=data[k];
    				for(j=k-temp;j>=0&&data[j]>i;j-=temp)
    				{
    					data[j+temp]=data[j];
    				}
    				data[j+temp]=i;
    			}
    		}
    		temp/=2;
        }
    }
    
    //堆排序
    //在data[s...m]所构成的一个元素序列中，除了data[s]外，其余元素均满足大顶堆的定义
    void HeapAdjust(int data[],int s,int m)
    {
    	int i,temp;
    	for(i=2*s+1;i<=m;i=2*i+1)
    	{
    		if(i<m&&data[i]<data[i+1])i++;
    		if(data[s]<data[i])
    		{
    			temp=data[s];
    			data[s]=data[i];
    			data[i]=temp;
    		}else{
    			break;
    		}
    		s=i;
    	}
    }
    
    void HeapSort(int data[], int n)
    {
    	int i,j;
    	for(i=n/2-1;i>=0;i--)
    	{
    		HeapAdjust(data,i,n-1);
    	}
    	for(i=n-1;i>=1;i--)
    	{
    		j=data[i];data[i]=data[0];
    		data[0]=j;
    		HeapAdjust(data,0,i-1);
    	}
    }
    int main()
    {
        int i;
        int data1[8]={11,55658,5,6576,89,5,68,9};
        int data2[8],data3[8],data4[8];
        memcpy(data2,data1,sizeof(int)*8);
    	memcpy(data3,data1,sizeof(int)*8);
    	memcpy(data4,data1,sizeof(int)*8);
        InsertSort(data1,8);
        cout<<"插入排序:"<<endl;
        for(i=0;i<8;i++){
            cout<<data1[i]<<" ";
        }
        cout<<endl;
        SelectSort(data2,8);
        cout<<"选择排序:"<<endl;
        for(i=0;i<8;i++){
            cout<<data2[i]<<" ";
        }
        cout<<endl;
    	cout<<"希尔排序"<<endl;
    	ShellSort(data3,8);
    	for(i=0;i<8;i++){
            cout<<data3[i]<<" ";
        }
        cout<<endl;
    	cout<<"堆排序"<<endl;
    	ShellSort(data4,8);
    	for(i=0;i<8;i++){
            cout<<data4[i]<<" ";
        }
        cout<<endl;
        return 0;
    }