一道被羞辱过N次的题目

快速排序

quick_sort.rb

def quick_sort a
  b = a.pop
  return [] if b.nil?
  left = quick_sort(a.select{|e|e<=b})
  right = quick_sort(a.select{|e|e>b})
  return left + [b] + right
end

def quick_sort(array)
  return array if array.size < 2
  left, right = array[1..-1].partition { |y| y <= array.first }
  quick_sort(left) + [array.first] + quick_sort(right)
end

def qs a
  (b = a.pop) ? qs(a.select { |e| e<=b }) + [b] + qs(a.select { |e| e>b }) : []
end

a = [2,5,1,53,857,23,8658]
p quick_sort(a)

quick_sort.c

#include <stdio.h>

void sort(int *a, int left, int right)
{
    if(left >= right)
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j)
    {
        while(i < j && key <= a[j])
        { 
          j--; 
        }
        a[i] = a[j];
        while(i < j && key >= a[i])
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    sort(a, left, i - 1);
    sort(a, i + 1, right);
}


int main(int argc, char const *argv[])
{
  int a[] = {1,2,3,4,5,0,9,8,7,6};
  sort(a, 0, 9);
  printf("[");
  for (int i = 0; i <= 9; i++)
  {
    printf("%d ", a[i]);
  }
  printf("]");
  return 0;
}

quick_sort.py

def quickSort(L, low, high):
    i = low
    j = high
    if i >= j:
        return L
    key = L[i]
    while i < j:
        while i < j and L[j] >= key:
            j = j-1
        L[i] = L[j]
        while i < j and L[i] <= key:
            i = i+1
        L[j] = L[i]
    L[i] = key
    quickSort(L, low, i-1)
    quickSort(L, j+1, high)
    return L

a = [2,5,1,6,8,33,785,473,36,435,23,5235,4]
print quickSort(a, 0, len(a)-1)

quick_sort.go

package main

import "fmt"

func qsort(data []int) {
  if len(data) <= 1 {
    return
  }
  mid, i := data[0], 1
  head, tail := 0, len(data)-1
  for i = 1; i <= tail; {
    if data[i] > mid {
      data[i], data[tail] = data[tail], data[i]
      tail--
    } else {
      data[i], data[head] = data[head], data[i]
      head++
      i++
    }
  }
  data[head] = mid
  qsort(data[:head])
  qsort(data[head+1:])
}

func main() {
  a := []int{1, 2, 3, 4, 5, 10, 9, 8, 7, 6}
  qsort(a)
  fmt.Println(a)
}