快速排序的算法(c语言实现)-蒲公英云

快速排序的算法(c语言实现)

下面是我们华信王老师讲的快排算法

用的头文件和任意数据类型

#include <stdio.h>
#include <stdlib.h>
typedef int elemtype;

//快排的核心算法

int partation(elemtype arr[],int i,int j)
{ 
    elemtype temp = arr[i];//temp是枢轴，即分界线
    while(i < j){ 
        while(j > i && arr[j] > temp){ 
            j --;
        }
        arr[i] = arr[j];
        while(j > i && arr[i] < temp){ 
            i ++;
        }
        arr[j] = arr[i];
    }
    arr[i] = temp;
    return i;
}

//递归实现完整排序

void QuickSort(elemtype arr[],int i,int j)
{ //i表示数组的第一个元素下表，j表示最后一个元素下标
    int k;//接收partation()的返回值
    if(i < j){ 
        k = partation(arr,i,j);
        QuickSort(arr,i,k - 1);
        QuickSort(arr,k + 1,j);
    }
}

//完整代码

typedef int elemtype;
//快速排序的核心代码
int partation(elemtype arr[],int i,int j)
{ 
    elemtype temp = arr[i];
    while(i < j){ 
        while(j > i && arr[j] > temp){ 
            j --;
        }
        arr[i] = arr[j];
        while(j > i && arr[i] < temp){ 
            i ++;
        }
        arr[j] = arr[i];
    }
    arr[i] = temp;
    return i;
}
//递归实现
void QuickSort(elemtype arr[],int i,int j)
{ 
    int k;
    if(i < j){ 
        k = partation(arr,i,j);
        QuickSort(arr,i,k - 1);
        QuickSort(arr,k + 1,j);
    }
}
int main()
{ 
    int num,i,k;
    printf("请输入您总数据的个数:");
    scanf("%d",&num);
    elemtype arr[num];
    printf("请输入数据:");
    for(i = 0;i < num;i ++){ 
        scanf("%d",&arr[i]);
    }
    printf("数据输入成功!您可\n输入1:查看排序后内容\n输入2:查看未排序内容\n输入0:退出!\n");
    while(1){ 
        printf("\n请输入:");
        scanf("%d",&k);
        switch(k){ 
        case 1:
            { 
                QuickSort(arr,0,num - 1);
                for(i = 0;i < num;i ++){ 
                  printf("%d ",arr[i]);
                }
                break;
            }
        case 2:
            { 
                for(i = 0;i < num;i ++){ 
                  printf("%d ",arr[i]);
                }
                break;
            }
        case 0:
            return;
        }
    }
}