快速排序

2019-04-24 23:20:39

八大排序算法

今天才发现了有插入代码这个选项，以后可以更方便啦；水平线则个选择不知道怎么删除.....

排序算法：内部排序外部排序

内部排序：插入排序（直接插入排序希尔排序）选择排序（简单选择排序堆排序）交换排序（冒泡排序快速排序）归并排序基数排序

外部排序

 1   int n;
 2  void quicksort(int* a, int p,int r)
 3  {
 4      int i = p;
 5      int j = r;
 6      int temp = a[p];    
 7     
 8     while(i < j)    {
 9          // 越过不小于基准值的数据 
10         while( a[j] >= temp && j > i ) j--;
11          
12          if( j > i )
13         {
14              a[i] = a[j];
15              i++;
16              
17              // 越过小于基准值的数据 
18              while(a[i] <= temp && i < j )  i++;
19             if( i < j )
20              {
21                a[j] = a[i];
22                  j--;
23              }
24          }        
25      }
26      a[i] = temp; 
27      
28      for(int k = p; k <= r;k++)
29     {
30          if( k == i ) 
31          {
32             printf("(%d) ",a[k]);
33              continue;
34         }
35         printf("%d ",a[k]);
36     } 
37     printf("
");
38      
39      if( p < (i-1)) quicksort(a,p,i-1);
40      if((j+1) < r ) quicksort(a,j+1,r);    
41  }
42  
43  int main(int argc, char* argv[])
44  {
45      int a[ n];
46      int n;    
47  
48      printf("Input total numbers: ");
49      scanf("%d",&n);
50  
51      
52      for(int i = 0; i < n;i++)
53      {
54          scanf("%d",&a[i]);
55      }
56     
57      printf("Divide sequence:
");
58      quicksort(a,0,n-1);
59      
60      printf("The sorted result:
");
61      for(int i = 0; i < n;i++)
62      {
63         printf("%d ",a[i]);
64     } 
65      printf("
");
66         
67      
68      return 0;
69  }

#define MAX_NUM 80 //先定义数组长度，后续使用不完，容易造成空间浪费

void quicksort(int* a, int p,int r)    //快速排序算法
{
     int i = p;
     int j = r;
    int temp = a[p];    //将第一位数作为基准

    while(i < j)    {
         // 越过不小于基准值的数据
        while( a[j] >= temp && j > i )

   j--;

         if( j > i )
        {
             a[i] = a[j];    //交换数组的内容，将较小值换在左边
             i++;

             // 越过小于基准值的数据
             while(a[i] <= temp && i < j )

i++;
            if( i < j )
             {
               a[j] = a[i];
                 j--;
             }
         }
     }
     a[i] = temp;

     for(int k = p; k <= q;k++)
    {
         if( k == i )
         {
            printf("(%d) ",a[k]);
             continue;
        }
        printf("%d ",a[k]);
    }
    printf(" ");

     if( p < (i-1)) quicksort(a,p,i-1);
     if((j+1) < q ) quicksort(a,j+1,q);
}

int main(int argc, char* argv[])
{
     int a[MAX_NUM];
     int n;

     printf("Input total numbers: ");
     scanf("%d",&n);

     if( n > MAX_NUM )
n = MAX_NUM;

     for(int i = 0; i < n;i++)
     {
         scanf("%d",&a[i]);
     }

     printf("Divide sequence: ");
     quicksort(a,0,n-1);

     printf("The sorted result: ");
     for(int i = 0; i < n;i++)
     {
        printf("%d ",a[i]);
    }
     printf(" ");


     return 0;
}

2019-04-27 17:48:38

请教版本，算法基本理解，但是不足之处是并没有输出每一次划分的数组，后续会改进了继续更新。

#include<stdio.h>
void quick_sort(int *arr,int start,int end);
int partition(int *arr,int start,int end);

int main(){
    int n;
    int arr[n];
    int i=0;
    printf("please input number: ");
    scanf("%d",&n);
    for(i=0;i<=n-1;i++){
    scanf(" %d",&arr[i]);
}
       
    quick_sort(arr,0,n-1);
    for(int i=0;i<n;i++){
    printf(" %d",arr[i]); 
 }
}
void quick_sort(int *arr,int start,int end){
    if(start<end){
        int p=partition(arr,start,end);
        
        quick_sort(arr,start,p-1);
        quick_sort(arr,p+1,end);
         
    }
}
int partition(int *arr,int start,int end){
    int n;
    int i=start;
    int j=end+1;
    int x=arr[start];
    
    while(1){
        while(arr[++i]<x && i<end);
        while(arr[--j]>x);
        if(i>=j){
        break;
    }
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    arr[start]=arr[j];
    arr[j]=x;
    return j;

}

#include<stdio.h>
void quick_sort(int *arr,int start,int end); // 声明两个函数
int partition(int *arr,int start,int end); //int *arr相当于int arr[]

/*主函数定义数组长度，先输入想要排序的数组长度，再一次我输入数组的值，调用quick_sort算法，进行排序。*/

int main(){
int n;
int arr[n];
int i=0;
printf("please input number: ");
scanf("%d",&n);
for(i=0;i<=n-1;i++){
scanf(" %d",&arr[i]);
}

    quick_sort(arr,0,n-1);
for(int i=0;i<n;i++){
printf(" %d",arr[i]);
}
}
void quick_sort(int *arr,int start,int end){
if(start<end){
  int p=partition(arr,start,end);

  quick_sort(arr,start,p-1);
  quick_sort(arr,p+1,end);

}
}
int partition(int *arr,int start,int end){

int i=start;
int j=end+1;
int x=arr[start];    //定义初始值start为第一次划分的基准

while(1){
  while(arr[++i]<x && i<end);
  while(arr[--j]>x);
  if(i>=j){ 当i与j指向同一元素或者i在j右边时，跳出循环。
  break;
}
  int temp=arr[i];    //若没有跳出循环，找比基准值大i对应的数值与比基准值小j对应的数值，交换a[i]与a[j]的值，
  arr[i]=arr[j];
  arr[j]=temp;
}
arr[start]=arr[j]; //将j对应的数值作为新的基准值，再次比较。
arr[j]=x;    //将基准值放在j的位置
return j;
}