c语言，java，和ruby堆排序实现，ruby堆排序,C/C++ 实现堆排序v

c语言，java，和ruby堆排序实现，ruby堆排序,C/C++ 实现堆排序v

C/C++ 实现堆排序

void heapsort(int arr[], unsigned int N)  {      unsigned int n = N, i = n/2, parent, child;      int t;      for (;;) { /* Loops until arr is sorted */          if (i > 0) { /* First stage - Sorting the heap */              i--;           /* Save its index to i */              t = arr[i];    /* Save parent value to t */          } else {     /* Second stage - Extracting elements in-place */              n--;           /* Make the new heap smaller */              if (n == 0) return; /* When the heap is empty, we are done */              t = arr[n];    /* Save last value (it will be overwritten) */              arr[n] = arr[0]; /* Save largest value at the end of arr */          }          parent = i; /* We will start pushing down t from parent */          child = i*2 + 1; /* parent's left child */          /* Sift operation - pushing the value of t down the heap */          while (child < n) {              if (child + 1 < n  &&  arr[child + 1] > arr[child]) {                  child++; /* Choose the largest child */              }              if (arr[child] > t) { /* If any child is bigger than the parent */                  arr[parent] = arr[child]; /* Move the largest child up */                  parent = child; /* Move parent pointer to this child */                  //child = parent*2-1; /* Find the next child */                  child = parent*2+1; /* the previous line is wrong*/              } else {                  break; /* t's place is found */              }          }          arr[parent] = t; /* We save t in the heap */      }  }

Java 实现堆排序

public class HeapSort{    public static <T extends Comparable<? super T>> void sort(T[] table)    {        buildHeap(table);        shrinkHeap(table);    }    private static <T extends Comparable<? super T>> void buildHeap(T[] table)    {        for (int child = 1; child < table.length; child++)        {            int parent = (child - 1) / 2;            while (parent >= 0 && table[parent].compareTo(table[child]) < 0)            {                swap(table, parent, child);                child = parent;                parent = (child - 1) / 2;            }        }    }    private static <T extends Comparable<? super T>> void shrinkHeap(T[] table)    {        for (int n = table.length-1; n >= 0; n--)        {            swap(table, 0, n);            int parent = 0;            while (true)            {                int leftChild = 2 * parent + 1;                if (leftChild >= n)                    break; // no more children                int rightChild = leftChild + 1;                int maxChild = leftChild;                if (rightChild < n && table[leftChild].compareTo(table[rightChild]) < 0)                    maxChild = rightChild;                if (table[parent].compareTo(table[maxChild]) < 0)                {                    swap(table, parent, maxChild);                    parent = maxChild;                }                else                    break; // exit loop            }        }    }    private static void swap(Object[] table, int i, int j)    {        Object temp = table[i];        table[i] = table[j];        table[j] = temp;    }}

Ruby

def heap_sort(array)  n = array.size  a = [nil] + array             # heap root [0]=>[1]  (n / 2).downto(1) do |i|    down_heap(a, i, n)  end  while n > 1    a[1], a[n] = a[n], a[1]    n -= 1    down_heap(a, 1, n)  end  a.drop(1)                     # heap root [1]=>[0]enddef down_heap(a, parent, limit)  wk = a[parent]  while (child = 2 * parent) <= limit    child += 1  if child < limit and a[child] < a[child + 1]    break  if wk >= a[child]    a[parent] = a[child]    parent = child  end  a[parent] = wkenda = [35, -8, 11, 1, 68, 0, 3]p heap_sort(a)    #=> [-8, 0, 1, 3, 11, 35, 68]