插入排序、选择排序和快速排序的算法实现

曾经终败给现在 2022-07-14 09:40 165阅读 0赞

1.插入排序

#include<iostream>
    using namespace std;
    int main ()
    {
    	int i,j,k=1,a,n,m,number[100];
    	cout<<"please enter a number as n:\n";
    	cin>>n;
    	cout<<"please input n interge numbers :\n";
    	for(m=1;m<=n;m++)
    	{
    		cin>>number[m];
    	}
    	
    	for(i=2;i<=n;i++)
    	{
    		a=number[i];
    		j=i-1;
    		while(j>0 && number[j]>a)
    
    		{
    			number[j+1]=number[j];
    			j=j-1;
    		}
    		number[j+1]=a;
    	}
    	cout<<"排序后的数组：";
    	for(k=1;k<=n;k++)
    	{
    		cout<<number[k]<<" ";
    		
    	}
    	return 0;
    }

2.选择排序

#include <stdio.h>
    #include <math.h>
    #define MAX 100
    
    void swap(int*a,int*b)
    {
        int temp;
        temp=*a;
        *a=*b;
        *b=temp;
    }
    
    void sort(int s[], int n)
    {
        int i, j, min, temp;
        for (i = 0; i < n - 1; i++){
            min = i;
            for (j = i + 1; j < n; j++)
            if (s[j] < s[min])
                min = j;
            swap(&s[i], &s[min]);
        }
    }
     
    void main(void)
    {
        int i, n;
        int s[MAX];
        printf("请输入数组元素的个数n: ");
        scanf("%d", &n);
        printf("请输入待排序的数组: \n");
        for(i=0;i<n;i++)
        {
    	   scanf("%d",&s[i]);
    	}
        if (n < 1 || n > MAX){
            printf("Error\n");
        }
        sort(s, n);
        printf("排序后的数组为:\n");
        for (i = 0; i < n; i++)    
            printf("%d ", s[i]);
        printf("\n");
    }

3.快速排序

#include<iostream>
    #define MAX 100
    using namespace std;
    
    
    int Swap(int &a, int &b)
    {    
    	int temp;
    	temp = a;
    	a = b;
    	b = temp;
    	return 0;
    }
    
    //划分算法 
    int split(int A[],int low,int high )
    {
    	int i=low;
    	int x=A[low];
    	int j = high+1;
    	while(1)
    	{
    		while(A[++i]<x && i<high);
    		  while(A[--j]>x);
    		  if(i>=j) break;
    		Swap(A[i], A[j]);
    	}
    	A[low] = A[j];
    	A[j] = x;
    	return j;
    }
    
    //快速排序算法 
    void quicksort(int A[],int low,int high)
    {
    	if ( low < high )
    	{
    		int w=split(A,low,high);
    		quicksort(A,low,w-1);
    		quicksort(A,w+1,high);
    	}	
    }
    
    int main ()
    {   
        int i, n;
        int A[MAX];
        printf("请输入数组元素的个数n: ");
        scanf("%d", &n);
        printf("请输入待排序的数组: \n");
        for(i=0;i<n;i++)
        {
    	   scanf("%d",&A[i]);
    	}  
        quicksort(A,0,n-1);
        cout<<"排序后的序列为："<<endl;
         for( int k = 0; k < n; k++ )
           cout << A[k] << "  ";
           cout << endl;
    	return 0;
    }