排序(快速排序和堆排序)练习

  1 #include <iostream>
  2 
  3 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  4 //karllen
  5 //2015 4 18
  6 
  7 void quickSort(int *a,int low,int high); //快速排序
  8 void heapSort(int *a,int n);             //堆排序
  9 void eleSwap(int &a,int &b);             //交换数据
 10 int leftIndex(int index);                //返回左子节点的下标
 11 int rightIndex(int index);               //返回右子节点的下标
 12 void makeHeapMax(int *a,int length);     //建堆
 13 void maxHeapify(int *a,int index);       //下滤最大值
 14 static int heapSize = 0;                 //堆的规模
 15 
 16 //测试
 17 int main(int argc, char** argv)
 18 {
 19     int a[] = {4,9,3,5,7,5,9,2,1,8,10};
 20     int b[] = {4,9,3,5,7,5,9,2,1,8,10};
 21     int i = 0;
 22     quickSort(a,0,10);
 23     while(i<11)
 24     {
 25         std::cout<<a[i]<<" ";
 26         ++i;
 27     }
 28     int j = 0;
 29     heapSort(b,11);
 30     while(j<11)
 31     {
 32         std::cout<<b[j]<<" ";
 33         ++j;
 34     }
 35     return 0;
 36 }
 37 //快速排序
 38 void quickSort(int *a,int low ,int high)
 39 {
        if(a == NULL || low <0 || high < 0)
        return;
 40     if(low <high)
 41     {                           //自然递归返回条件
 42         int pivot, i, j;
 43         pivot = a[low];                      //暂且轴点等于第一个元素
 44         i = low;
 45         j = high;
 46         while(i<j)
 47         {
 48             while(i<j && a[j]>=pivot)
 49             {
 50                 --j;
 51             }
 52             if(i<j)
 53             a[i++] = a[j];
 54             while(i<j && a[i]<=pivot)
 55             {
 56                 ++i;
 57             }
 58             if(i<j)
 59             a[j--] = a[i];
 60         }
 61         a[i] = pivot;                        // 有序基准
 62         quickSort(a,low,i-1);                // 递归排序小于轴点的部分
 63         quickSort(a,i+1,high);               // 递归排序大于轴点的部分
 64     }
 65 }
 66 //交换函数
 67 void eleSwap(int &a,int &b)
 68 {
 69     int temp = a;
 70     a = b;
 71     b = temp;
 72 }
 73 //左子序
 74 int leftIndex(int index)
 75 {
 76     return (index<<1 )+1;
 77 }
 78 //右子序
 79 int rightIndex(int index)
 80 {
 81     return (index<<1 )+2;
 82 }
 83 
 84 //优先级大堆下滤算法
 85 void maxHeapify(int *a,int index)
 86 {
        if(a == NULL ||index <0)
        return;
 87     int largestIndex = 0;
 88     int left = leftIndex(index);
 89     int right = rightIndex(index);
 90     if(left < heapSize && a[left]>a[index])
 91     {
 92         largestIndex = left;
 93     }
 94     else
 95     {
 96         largestIndex = index;
 97     }
 98     if(right < heapSize && a[right]>a[largestIndex])
 99     {
100         largestIndex = right;
101     }
102     if(largestIndex != index)
103     {
104         eleSwap(a[index],a[largestIndex]);
105         maxHeapify(a,largestIndex);
106     }
107 }
108 
109 //建堆
110 void makeHeapMax(int *a,int length)
111 {
112     heapSize = length;
113     for(int i = ((length>>1 )-1 );i>=0 ;--i)
114     {
115         maxHeapify(a,i);
116     }
117 }
118 
119 //堆排序
120 void heapSort(int *a,int n)
121 {
122     makeHeapMax(a,n);
123     for(int i = n - 1;i>=1;--i)
124     {
125         eleSwap(a[0],a[i]);
126         --heapSize;
127         maxHeapify(a,0);
128     }
129 }

堆排序是优先级队列的体现之一，实现原理，将优先级最高者与最后元素交换，即提取最大者或者最小者至有序部分，然后调整无序部分使其重新构成堆，不断执行上述重复操作，直到无序部分元素为1，排序即可完成。

快速排序实现原则是利用轴点的特性，递归排序比轴点大的部分和比轴点小的部分，只到轴点两侧元素为1，此时自然有序，递归返回，快排即可实现。关键部分，求轴点。