其他三种排序：堆排序，归并排序，快速排序

//交换函数 void swap (int a[],int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

//打印函数 void printA (int *a,int len) { int i; for (i = 0; i < len; i++) { printf (“%-4d”,a[i]); } printf (“\n”); }

//堆排序主函数 void heapify (int *a, int i, int len) { int left = 2 * i + 1; int right = 2 * i + 2; int max = i;

if (left < len && a[left] > a[max]) max = left; if (right < len && a[right] > a[max]) max = right; if (max != i) { swap (a, i, max); heapify (a, max ,len); }

}

void heapSort (int *a, int len) { int i; for (i = len/2 - 1; i >= 0; i–) { heapify (a, i, len); }

for (i = len-1; i > 0; i--) { swap (a, 0, i); len--; heapify (a, 0, len); }

} //归并函数主函数，a 是数组，tmp 是缓冲区 void merge (int *a, int left, int mid, int right, int *tmp) { int i = left; int j = mid + 1; int k = 0; }

void mergeSort (int *a,int left,int right,int *tmp) { if (left >= right) return;

int mid = (left + right)/2; mergeSort (a,left,mid,tmp); //对左边进行排序 mergeSort (a,mid+1,right,tmp); //对右边进行排序 merge (a,left,mid,right,tmp); //将左右归并

}

//归并排序 int main() { int a[10] = {9,2,1,5,4,7,6,3,8,0}; int len = sizeof(a)/sizeof(a[0]);

int tmp[10]; mergeSort (a,0,len-1,tmp); printA (a,len); return 0;

}

int partition (int *a,int left,int right) //快速排序主函数 { int pivot = a[right]; int index = left; //若找到比基准值小的元素，交换 int i;

for (i = left;i < right; i++) { if (a[i] < pivot) { swap (a,i,index); index++; } } swap (a,index,right); return index;

}

void qSort (int *a,int left,int right) { if (left < right) { int pivot = partition (a,left,right); //对分区进行操作，找基准值下标 qSort (a,left,pivot-1); qSort (a,pivot+1,right); //对左右分区进行操作 } }

//快速排序 int main() { int a[10] = {9,2,1,0,4,7,6,3,8,5}; int len = sizeof(a)/sizeof(a[0]);

qSort (a,0,len-1); printA (a,len); return 0;

}