数据结构实验六：内部排序技术

内部排序——快速排序

#include<stdio.h>
#include<stdlib.h>
void myqsort( int *a, int low, int high)
{
     int i,j; 
     int c; 
    c=a[low]; 
    i=low; 
    j=high; 
     while(i<j) 
    { 
         while(a[j]>=c && i<j)--j; 
            a[i]=a[j]; 
         while(a[i]<=c && i<j)++i; 
            a[j]=a[i]; 
    } 
    a[i]=c; 
     if(i- 1>low) myqsort(a,low,i- 1); 
     if(high>i+ 1) myqsort(a,i+ 1,high);
}
int main()
{
     int a[ 30],i;
     for(i= 0;i< 20;i++)
        a[i]=rand()% 50;
     for(i= 0;i< 20;i++)
    printf( " %d  ",a[i]);
    printf( " \n ");
    myqsort(a, 0, 20);
     for(i= 0;i< 20;i++)
    printf( " %d  ",a[i]);
    printf( " \n ");        
}


内部排序——堆排序
#include <stdio.h>
#include <math.h>
#define LEFT(i) ((i)<<1)
#define RIGHT(i) (((i)<<1)+1)
void max_heapify( int a[],  int i,  int heapsize);
void heap_sort( int a[],  int heapsize);
void build_max_heap( int a[],  int heapsize);
void exchange( int *x,  int *y);
// 交换两个数的值
void exchange( int *x,  int *y) 
{
     int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
// 保持最大堆性质
void max_heapify( int a[],  int i,  int heapsize) 
{    
     int left, right, largerest;
    left = LEFT(i);
    right = RIGHT(i);
     if (left <= heapsize && a[left] > a[i])
    {
        largerest = left;
    }
     else
    {        
        largerest = i;
    }
     if (right <= heapsize && a[right] > a[largerest])
    {
        largerest = right;
    }
     if(largerest != i) 
    {        
        exchange(&a[i], &a[largerest]);
        max_heapify(a, largerest, heapsize);
    }
}
// 建造最大堆
void build_max_heap( int a[],  int heapsize) 
{    
     int i;
     for (i = ( int) ceil(heapsize/ 2); i >=  1 ; i--)
    {
        max_heapify(a, i, heapsize);
    }
}
// 堆排序
void heap_sort( int a[],  int heapsize) 
{    
     int i;
     // build heap
    build_max_heap(a, heapsize);
     while(heapsize >  1)
    {
         // exchange max
        exchange(&a[ 1], &a[heapsize]);
        heapsize--;
        max_heapify(a,  1, heapsize);
    }
}
int main() 
{    
     int a[] = 
    {
         0,  2,  0,  23,  38,  19,
         98,  203,  803,  3,  78,
         34,  68,  49,  9,  55};
     int array_size =  sizeof(a) / sizeof( int);
     int i, heapsize;
    heapsize = array_size -  1;
    heap_sort(a, heapsize);
     // 打印排序后的数组
     for (i =  1; i <= heapsize ; i++)
    {
        printf( " %d\t ", a[i]);
    }
    printf( " \n ");
    getchar();
     return  0;
}