Linux C堆排序(升序)实现
堆排序是利用最大(小)堆实现的排序。首先构造成最大(最小堆),然后将第一个节点和最后一个节点交换,使最后一个节点(n)的值为最大(最小),再将除最后节点的数据进行堆排序,再将第一个节点与(n-1)个节点交换,依此循环n-1次,最终得到升序(降序)有序序列。
复杂度:O(N * logN)
稳定性:不稳定
测试结果:
1.
Before sort 5 6 3 1 2 4 //排序前 6 5 4 1 2 3 //最大堆 After sort 1 2 3 4 5 6 //排序后
2.
Before sort 4 6 2 1 3 5 6 4 5 1 3 2 After sort 1 2 3 4 5 6
源码:
my_heap_sort.c:
#include <stdio.h> #define ARRAY_N 6 int array[ARRAY_N]={5, 6 , 3, 1, 2, 4}; void swap(int a[], int i, int j) { int tmp = 0; tmp = a[i]; a[i] = a[j]; a[j] = tmp; } void max_heap_adjust(int a[], int start, int end) { int root = start; int left = 2 * root + 1; int right = 0; int tmp = 0; for (; left <= end; root=left, left= 2 *root + 1) { right = left + 1; if (left < end && a[left] < a[right]) { left++; } if (a[root] < a[left]) { swap(a, root, left); } else { break; } } } void heap_sort_asc(int a[], int n) { int i; for (i = n / 2 - 1; i >= 0; i--) max_heap_adjust(a, i, n-1); show_list(array, ARRAY_N); for (i = n - 1; i > 0; i--) { swap(a, 0, i); max_heap_adjust(a, 0, i-1); } } int show_list(int array[], int n) { int i = 0; for (i=0; i < ARRAY_N; i++) { printf("%5d", array[i]); } printf(" "); return 0; } int main(void) { printf("Before sort "); show_list(array, ARRAY_N); heap_sort_asc(array, ARRAY_N); printf("After sort "); show_list(array, ARRAY_N); return 0; }
上一篇:
IDEA上Java项目控制台中文乱码