【竞赛】排序算法的最快实现

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【java2000_net】截止到2008-06-23 14:14:03的历史汇总数据(不包括此帖)：
发帖数:162                发帖分:17891
结贴数:159                结贴分:17271
未结数:3                  未结分:620
结贴率:98.15 %            结分率:96.53 %
值得尊敬

我先提供一个
  public static int[] sort(int[] nums) {
    int size = nums.length;
    int tmp;
    for (int i = 0; i < size; i++) {
      for (int j = i; j < size; j++) {
        if (nums[i] > nums[j]) {
          tmp = nums[i];
          nums[i] = nums[j];
          nums[j] = tmp;
        }
      }
    }
    return nums;
  }在我的机器上运行时间： 32281

Arrays.sort(nums);为什么不用这个呢，跑了下，好像挺快的！

public static int[] directInsertSort(int[] nums) {
    // 已经排序的长度
    int leng = 1;
    // 标记
    int ;    for (int i = 1; i < nums.length; i++) {
       = nums[leng];// 将未排序列的第一个元素暂存
       if (nums[i] < nums[i - 1]) {// leng处小于已排序部分的最大数，需要插入
         for (int j = 0; j < leng; j++) {// 将插入已排序部分的适当位置
           if ( <= nums[j]) {// 不大于nums[j]
            for (int k = leng - 1; k >= j; k--) {// 移动
              nums[k + 1] = nums[k];
          }
          nums[j] = ;
          break;// 跳出
         }
       }
      }
      leng++;// 已排序部分的长度加1
    }// for
    return nums;
  }

……为什么第一个念头是去看Arrays.sort的源码

用归并排序吧，不过俺不会Java...

public static int[] sort(int[] nums) {
Arrays.sort(nums);
return nums;
}
//不知道用JDK的工具可不可以,这个是用快速排序算法实现的,应该是最快的.

不会java
只会vbs，凑凑热闹哈
Function QSort(nums)
        Dim L, R, tmp
        L = 1
        R = ubound(nums)   'Get the arrays length
        tmp = nums(L)        Do Until L >= R
                While (Data(R) > tmp And R > L)
                        R = R - 1
                Wend
                If R > L Then
                        Data(L) = Data(R)
                        Data(R) = tmp
                        L = L + 1
                End If
                While (Data(L) < tmp And R > L)
                        L = L + 1
                Wend
                If R > L Then
                        Data(R) = Data(L)
                        Data(L) = tmp
                        R = R - 1
                End If
        Loop
QSort = nums
End Function

好像著名的有九种。
1.插入排序
2. 冒泡排序
3选择排序
四 Shell排序
五快速排序-----一般分如下步骤：
1）选择一个枢纽元素（有很对选法，我的实现里采用去中间元素的简单方法）
2）使用该枢纽元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。并把枢纽元素放在合适的位置。
3）根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。
快速排序的核心在于分割算法，也可以说是最有技巧的部分。
6.归并排序
7堆排序
8.桶式排序
9.基数排序
基数排很多的元素，效率不错。

居然又有人用Sort来说呢，再无语一次！

有个建议：只靠随机生成一个数列用来排序的话，可能会有一点不公平因为大家知道，不同的算法有不同的优点比如：如果数列本身有序，用冒泡的只需要一趟检查就可以搞定，而用快速排序就需要log(n) 趟所以最好综合考虑一下用不同性质的数列去测试这个算法综合评估这样会更公平一点

如果是整数，那么计数排序法是最快的时间是o(n)
public class MarquisSort
{
private static int[] resultData;

public static void main( String[] args )
{ int MAX = 100000;
int[] nums = new int[ MAX ];
Random r = new Random( 20080623 );
for( int i = 0; i < MAX; i++ )
{
nums[ i ] = r.nextInt( MAX );
}
long begin = System.currentTimeMillis();
int[] data = sort( nums );
long end = System.currentTimeMillis();
System.out.println( ( end - begin ) ); // 以这个时间为标准，越小越好。

} public static int[] sort( int[] nums )
{ // 您的排序代码放在这里啦
resultData = new int[nums.length];
countingSort( nums, resultData, getMaxInt( nums ) );
return resultData;
}

private static int getMaxInt( int[] data )
{
int max = 0;
for( int i : data )
{
if( i > max )
{
max = i;
}
}
return max;
}

private static void countingSort( int[] oriData, int[] resultData, int k )
{
int[] assistData = new int[ k + 1 ];

for( int i = 0; i < assistData.length ; i++ )
{
assistData[ i ] = 0;
}

for( int j = 0; j < oriData.length ; j++ )
{
assistData[ oriData[ j ] ] = assistData[ oriData[ j ] ] + 1;
} for( int i = 1; i < assistData.length ; i++ )
{
assistData[ i ] = assistData[ i ] + assistData[ i - 1 ];
} for( int j = oriData.length - 1 ; j >= 0 ; j-- )
{
resultData[ assistData[ oriData[ j ] ] - 1 ] = oriData[ j ];
assistData[ oriData[ j ] ] = assistData[ oriData[ j ] ] - 1;
}
}}
在我的电脑上运行时间是： 16

static int doPartition(int key,int left,int right){
int leftScan = left - 1;
int rightScan = right + 1;
int count = 0;
while(true){
while((++count) > 0&&leftScan < right&&arrNums[++leftScan] < key)
;
while((++count) > 0&&rightScan > left&&arrNums[--rightScan] > key)
;
if(leftScan > rightScan){
break;
}
else{
swap(leftScan,rightScan);
}
}
//System.out.println(count);
return rightScan;
}
/**
* 快速排序
* @param key
* @param left
* @param right
*/
static void quickSort(int key,int left,int right){
//int i;
if(left >= right)
return;
i = doPartition(key,left,right);
quickSort(arrNums[(left + i) / 2],left,i );
quickSort(arrNums[(i + right) / 2],i + 1,right);
}
注：copy来的代码

  /**
   * 快速排序法
   *
   * @param array
   * @param star
   *          将要进行快速排序的第一个元素位置(下标)
   * @param end
   *          将要进行快速排序的最后一个元素位置(下标)
   */
  public static void quickSort(int[] array, int star, int end) {
    // 记录原来的位置
    int priStar = star;
    int priEnd = end;
    if (star == end) {// 只有一个元素
      return;
    } else {
      int key = array[star]; // 以第一个元素作为关键数据
      int tem = 0; // 交换数据时用所的中间变量
      while (star < end) {
        while (star < end && array[end] >= key) {// 从最后一个元素开始找第一个比key小的元素
          end--;
        }
        if (star != end) {// 两都不等，说明找到,交换
          tem = array[star];
          array[star] = array[end];
          array[end] = tem;
        }
        while (star < end && array[star] <= key) {// 从第一个元素开始找第一个比key大的元素
          star++;
        }
        if (star != end) {// 两都不等，说明找到,交换
          tem = array[star];
          array[star] = array[end];
          array[end] = tem;
        }
      }// while
      if (priStar < star - 1) { // 如果关键值不是处于第一位，则对关键值前一部分进行递归排序
        quickSort(array, priStar, star - 1);
      }
      if (priEnd > end + 1) { // 如果关键值不是牌最后一位，则对关键值后面的部分进行递归排序
        quickSort(array, end + 1, priEnd);
      }
    }
  }
以前写的,不符题目要求,但真的很快,在我的电脑上运行没有超过三位数

public static int[] sort(int[] nums) {
Arrays.sort(nums); return nums;
}

package com.ew.test;import java.util.Random;public class nu {
  public static void main(String[] args) {
    int MAX = 100000;
    int[] nums = new int[MAX];
    Random r = new Random(20080623);
    for (int i = 0; i < MAX; i++) {
      nums[i] = r.nextInt(MAX);
    }
    long begin = System.currentTimeMillis();
    sort(nums,0,99999);
    for(int i=0;i<nums.length;i++)
    {System.out.println(nums[i]);
    }
    long end = System.currentTimeMillis();
    System.out.println((end - begin)); // 以这个时间为标准，越小越好。
  }  public static int[] sort(int[] nums, int left,int right)
  {

  int i,j;
  int middle,Temp;
  i = left;
  j = right;
  middle = nums[(i+j)/2];
  do{
  if((nums[i]<middle) && (i<right))
  i++;

  if((nums[j]>middle) && (j>left))
  j--;

  else if(nums[i]>=nums[j])
  {
  Temp = nums[i];
  nums[i] =nums[j];
  nums[j] = Temp;
  i++;
  j--;
  }
  }while(i<=j);   if(left<j)
  sort(nums,left,j);   if(right>i)
  sort(nums,i,right);

  return nums;
  }

}
快排

void QSort(int in[], int l, int r)
{
while (l<r)
{
int p = in[l], i = l, j = r + 1,t;
do{
while(--j,in[j]>p);
while(++i,in[i]<p);
if (i<j) t=in[i],in[i]=in[j],in[j]=t;
}while(i<j);//减少i,j的比较,经分析,在有大量元素相同的情况下,效率较低
in[l]=in[j],in[j]=p;
QSort(in, l, j-1);
l=j+1;
}
}void QSort(int a[],int l,int r)
{
while (l < r)
{
int i = l - 1, p =  a[r], t;
for (int j = l; j < r; ++j)
(a[j]<=p)&&(++i,t=a[i],a[i]=a[j],a[j]=t);
(++i,t=a[i],a[i]=a[j],a[j]=t);
                //算法导论提供的算法,大多数情况下适用
QSort(a, l, i-1);
l = i + 1;
}
} void QSort(int in[],int l,int r)
{
while (l<r)
{
int i=l, j=r, temp=in[i];
while(i<j)
{
while((in[j]>temp)&&(j>i)) --j;
if(j>i) in[i++]=in[j];
while((in[i] <=temp)&&(j>i)) ++i;
if(i<j)  in[j--]=in[i];
}
                //上面的算法有i,j的比较,在元素的交换代价较大的情况下适用
in[i]=temp;
QSort(in, l, i-1);
l = i+1;
}
}
//以上算法均使用尾递归的技巧
//可以改进为先递归具有较小长度的部分
//以上算法均没有考虑元素的序关系
//1.只有<的关系
//2.只有<=的序关系
//3.其它所有可能的为元素定义的关系
//在考虑序关系的情况下,又有很多可以考虑的
//因为如果只有<关系,那么可以定义出来>=关系即对<的结果进行逻辑非运算
//然而,在程序里不能出现 <= ,因为排序的元素不一定满足非严格弱序关系.
//总之,根本元素概念的不同,根本可能排序的元素的不同,进行操作的代价不同
//可以有不同的算法,所以楼主所提的"最快实现",是不大恰当的,应该给出一定的条件

这是我以前（c++）写的，我把核心的贴上来package temporary;import java.util.Random;public class Sort {

static int MAX = 100000;
static  int[] _data = new int[MAX];
public static void main(String[] args) {

    Random r = new Random(20080623);
    for (int i = 0; i < MAX; i++) {
     _data[i] = r.nextInt(MAX);
    }
    long begin = System.currentTimeMillis();
    qSort(0,MAX-1);
    long end = System.currentTimeMillis();
    System.out.println("consume time is: "+(end - begin)); // 以这个时间为标准，越小越好。
}

static void qSort(int begin, int end)
{
if (begin<end)
{
int q = partition(begin,end);
qSort(begin,q-1);
qSort(q+1,end);
}
}

static int partition(int begin, int end)
{
int i = begin;
int j = end+1;
int firstdata  = _data[begin];
while (true)
{
while (i<end&&(_data[++i]<firstdata));
while (j>0&&(_data[--j]>firstdata));
if (i>=j)
{
break;
}
int temp;
temp = _data[i];
_data[i] = _data[j];
_data[j] = temp;
}
_data[begin] = _data[j];
_data[j] = firstdata;
return j;
}

static void randomSort(int begin,int end)
{
if (begin<end)
{
int q = randomPartition(begin,end);
randomPartition(begin,q-1);
randomPartition(q+1,end);
}
} static int randomPartition(int begin,int end)
{
Random r = new Random(end+1);
int i = begin + r.nextInt();
System.out.println(i);
int temp;
temp = _data[i];
_data[i] = _data[begin];
_data[begin] = temp;
return partition(begin,end);
}}我在我机子上测试为:最好是15，最差是31
配置如下：内存1G，cpu： AMD 3600+双核，硬盘：wd160G

public static int[] sort(int[] nums) {
for(int i=1;i<nums.length;i++){
    for(int j=0;j<i;j++){
     if(nums[j]>nums[i]){
     nums[i]=nums[i]+nums[j];
     nums[j]=nums[i]-nums[j];
     nums[i]=nums[i]-nums[j];
     }
    }
}
    return nums;
}

//用的快速排序
public static void sort(int[] nums) {
        if (nums.length <= 1) {
            return;
        }
        sort(nums, 0, nums.length - 1);
    }
    public static void sort(int[] nums, int start, int end) {
        if (start < 0 || end >= nums.length || end - start <= 0) {
            return;
        }         int left = start;
        int right = end - 1;
        int pivot = nums[end];
        while (left < right) {
            if (nums[left] <= pivot) {
                left++;
                continue;
            }
            if (nums[right] > pivot) {
                right--;
                continue;
            }
            change(nums, left++, right);
        }         if (nums[left] < pivot) {
            left++;
        }
        change(nums, left, end);
        sort(nums, start, left - 1);
        sort(nums, left + 1, end);     }
    public static void change(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

public static int[] sort(int[] nums) {
// 您的排序代码放在这里啦
quickSort(nums,0,nums.length-1);
return nums;
}

private static void quickSort(int [] nums,int low,int high){
int midNum,scanUp,scanDown,mid;
if(high-low<=0)return;
if(high-low==1){
if(nums[high]<nums[low])swap(nums,low,high);
return;
}
mid=(low+high)/2;
midNum=nums[mid];
swap(nums,mid,low);
scanUp=low+1;
scanDown=high;
do{
while(scanUp<=scanDown && nums[scanUp]<=midNum)scanUp++;
while(midNum<nums[scanDown])scanDown--;
if(scanUp<scanDown)swap(nums,scanUp,scanDown);
}while(scanUp<scanDown);
nums[low]=nums[scanDown];
nums[scanDown]=midNum;
if(low<scanDown-1)quickSort(nums,low,scanDown-1);
if(scanDown+1<high)quickSort(nums, scanDown+1, high);
} private static void swap(int [] nums,int i, int j) {
int t=nums[i];nums[i]=nums[j];nums[j]=t;
}
//快速排序算法,就是他妈的快.

import java.util.Random;class Sort {
public static void main(String[] args) {
int MAX = 100000;
int[] nums = new int[MAX];
Random r = new Random(20080623);
for (int i = 0; i < MAX; i++) {
nums[i] = r.nextInt(MAX);
}
long begin = System.currentTimeMillis();
sort(nums);
long end = System.currentTimeMillis();
System.out.println((end - begin)); // 以这个时间为标准，越小越好。
} public static int[] sort(int[] nums) {
MaxHeap h = new MaxHeap();
h.init(nums);
for (int i = 0; i < nums.length; i++)
h.remove();
System.arraycopy(h.queue, 1, nums, 0, nums.length);
return nums;
} private static class MaxHeap { void init(int[] data) {
this.queue = new int[data.length + 1];
for (int i = 0; i < data.length; i++) {
queue[++size] = data[i];
fixUp(size);
}
} private int size = 0; private int[] queue; public int get() {
return queue[1];
} public void remove() {
swap(queue, 1, size--);
fixDown(1);
} private void fixDown(int k) {
int j;
while ((j = k << 1) <= size) {
if (j < size && queue[j] < queue[j + 1])
j++;
if (queue[k] > queue[j])
file: // 不/用交换
break;
swap(queue, j, k);
k = j;
}
} private void fixUp(int k) {
while (k > 1) {
int j = k >> 1;
if (queue[j] > queue[k])
break;
swap(queue, j, k);
k = j;
}
}
} public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}}
一般100秒左右

归并排序 30秒左右import java.util.Random;class Sort {
private static final int THRESHOLD = 10; public static void main(String[] args) {
int MAX = 100000;
int[] nums = new int[MAX];

Random r = new Random(20080623);
for (int i = 0; i < MAX; i++) {
nums[i] = r.nextInt(MAX);
}
long begin = System.currentTimeMillis();
sort(nums);
long end = System.currentTimeMillis();
System.out.println((end - begin)); // 以这个时间为标准，越小越好。
}

public static int[] sort(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
return nums;
} private static void mergeSort(int[] data, int[] temp, int l, int r) {
int i, j, k;
int mid = (l + r) / 2;
if (l == r)
return;
if ((mid - l) >= THRESHOLD)
mergeSort(data, temp, l, mid);
else
insertSort(data, l, mid - l + 1);
if ((r - mid) > THRESHOLD)
mergeSort(data, temp, mid + 1, r);
else
insertSort(data, mid + 1, r - mid); for (i = l; i <= mid; i++) {
temp[i] = data[i];
}
for (j = 1; j <= r - mid; j++) {
temp[r - j + 1] = data[j + mid];
}
int a = temp[l];
int b = temp[r];
for (i = l, j = r, k = l; k <= r; k++) {
if (a < b) {
data[k] = temp[i++];
a = temp[i];
} else {
data[k] = temp[j--];
b = temp[j];
}
}
} private static void insertSort(int[] data, int start, int len) {
for (int i = start + 1; i < start + len; i++) {
for (int j = i; (j > start) && data[j] < data[j - 1]; j--) {
swap(data, j, j - 1);
}
}
} public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}}

快速排序  比较快最快15秒（看RP的）import java.util.Random;class Sort {
private static int MAX_STACK_SIZE=4096;
    private static int THRESHOLD=10; public static void main(String[] args) {
int MAX = 100000;
int[] nums = new int[MAX];

Random r = new Random(20080623);
for (int i = 0; i < MAX; i++) {
nums[i] = r.nextInt(MAX);
}
long begin = System.currentTimeMillis();
sort(nums);
long end = System.currentTimeMillis();
System.out.println((end - begin)); // 以这个时间为标准，越小越好。
}

    public static int[] sort(int[] data) {
        int[] stack=new int[MAX_STACK_SIZE];

        int top=-1;
        int pivot;
        int pivotIndex,l,r;

        stack[++top]=0;
        stack[++top]=data.length-1;

        while(top>0){
            int j=stack[top--];
            int i=stack[top--];

            pivotIndex=(i+j)/2;
            pivot=data[pivotIndex];

            swap(data,pivotIndex,j);

            l=i-1;
            r=j;
            do{
                while(data[++l]<pivot);
                while((r!=0)&&(data[--r]>pivot));
                swap(data,l,r);
            }
            while(l<r);
            swap(data,l,r);
            swap(data,l,j);

            if((l-i)>THRESHOLD){
                stack[++top]=i;
                stack[++top]=l-1;
            }
            if((j-l)>THRESHOLD){
                stack[++top]=l+1;
                stack[++top]=j;
            }

        }
        insertSort(data);
return data;
    }

    private static void insertSort(int[] data) {
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                swap(data,j,j-1);
            }
        }
    } public static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}}

大家错了，针对与每一个元素是介于0~k之间整数，k=O(n),的话，计数排序还是最快的
原因是由于计数排序的思想是:记录小于每一个元素的元素个数

import java.util.Random;public class MarquisSort
{
    private static int[] resultData;

    public static void main( String[] args )
    {        int MAX = 100000;
        int[] nums = new int[ MAX ];
        Random r = new Random( 20080623 );
        for( int i = 0; i < MAX; i++ )
        {
            nums[ i ] = r.nextInt( MAX );
        }
        long begin = System.currentTimeMillis();
        int[] data = sort( nums );
        long end = System.currentTimeMillis();
        System.out.println( ( end - begin ) ); // 以这个时间为标准，越小越好。
        //for(int i=0;i<MAX;i++){
        // System.out.println(data[i]);
        //}        System.out.println(data[0]);
        System.out.println(data[1]);
        System.out.println(data[2]);
        System.out.println(data[3]);
        System.out.println(data[4]);
        System.out.println(data[MAX-4]);
        System.out.println(data[MAX-3]);
        System.out.println(data[MAX-2]);
        System.out.println(data[MAX-1]);


    }    public static int[] sort( int[] nums ){
        int max = getMax(nums)+1;
        int[] temp = new int[max];
        for(int i:nums){
         temp[i]++;
        }

        int pos=0;
        for (int i=0;i<max;i++){
         if (temp[i]>0){
         for(int l=0;l<temp[i];l++)
         nums[pos++]=i;
         }
        }
        return nums;
    }

    private static int getMax( int[] data )    {
        int max = 0;
        for( int i : data ){
            if( i > max ){
                max = i;
            }
        }
        return max;
    }
}

public static int[] sort( int[] nums ){
      int max = getMax(nums)+1;
      int[] temp = new int[max];
        for(int i:nums){
        temp[i]++;
        }

        int pos=0;
        for (int i=0;i <max;i++){
        if (temp[i]>0){
        for(int l=0;l <temp[i];l++)
        nums[pos++]=i;
        }
        }
        return nums;
    }

import java.util.Random;public class MarquisSort{
    private static int[] resultData;

    public static void main( String[] args )    {        int MAX = 100000;
        int[] nums = new int[ MAX ];
        Random r = new Random( 20080623 );
        for( int i = 0; i < MAX; i++ ){
            nums[ i ] = r.nextInt( MAX );
        }
        long begin = System.currentTimeMillis();
        int[] data = sort( nums );
        long end = System.currentTimeMillis();
        System.out.println( ( end - begin ) ); // 以这个时间为标准，越小越好。
    }    public static int[] sort( int[] nums ){
        int max = getMax(nums)+1;
        int[] temp = new int[max];
        for(int i:nums){
         temp[i]++;
        }
        int pos=0;
        for (int i=0;i<max;i++){
         if (temp[i]>0){
         for(int l=0;l<temp[i];l++)
         nums[pos++]=i;
         }
        }
        return nums;
    }

    private static int getMax( int[] data )    {
        int max = 0;
        for( int i : data ){
            if( i > max ){
                max = i;
            }
        }
        return max;
    }
}不好意思,重发一遍

因为是整数,所一第一反应是基数排序..
源码如下:
  public static int[] sort(int[]arr){
  int index [] = new int[10];
  int[] temp = new int[arr.length*10];
  int base = 1;
  int tempKey;

  //得到最大值
  int max = getMaxInt(arr);
  //基数比最大值大时退出循环
  while(base < max){
  for(int i= 0;i<arr.length;i++){
  tempKey = (arr[i]/base)%10;
  temp[tempKey*arr.length+index[tempKey]] = arr[i];//分到对应的桶中
  index[tempKey]++;
  }
  //整理桶
  for(int j = 0,count = 0;j<10;j++){
  for(int i=0;i<index[j];i++){
  arr[count] = temp[arr.length*j+i];
  count ++;
  }
  index[j]= 0;
  }

  base = base *10;//加大基数
  }

  return arr;
  }
  private static int getMaxInt( int[] data )
    {
        int max = 0;
        for( int i : data )
        {
            if( i > max )
            {
                max = i;
            }
        }
        return max;
    }

public static int[] sort(int[]arr){

  int index [] = new int[10];
  int[] temp = new int[arr.length*10];
  int base = 1;
  int tempKey;

  //得到最大值
  int max = getMaxInt(arr);
  //基数比最大值大时退出循环
  while(base < max){
  for(int i= 0;i<arr.length;i++){
  tempKey = (arr[i]/base)%10;
  temp[tempKey*arr.length+index[tempKey]] = arr[i];//分到对应的桶中
  index[tempKey]++;
  }
  //整理桶
  for(int j = 0,count = 0;j<10;j++){
  for(int i=0;i<index[j];i++){
  arr[count] = temp[arr.length*j+i];
  count ++;
  }
  index[j]= 0;
  }

  base = base *10;//加大基数
  }

  return arr;
  }
  private static int getMaxInt( int[] data )
    {
        int max = 0;
        for( int i : data )
        {
            if( i > max )
            {
                max = i;
            }
        }
        return max;
    } MAX = 100000; 47ms
MAX = 1000000; 500ms
MAX = 10000000; 内存溢出了,嘿嘿

刚测试了一下，数据量提高到1000000
基数排序法速度在203ms左右
快排速度在313ms左右
（本机）差距还是比较明显的。

import java.util.Random;
/*
* 快速排序算法，先对数组进行分割，然后使用递归调用分割
*
*
* */
public class T {
  public static void main(String[] args) {
    int MAX = 100000;
    int[] nums = new int[MAX];
    Random r = new Random(20080623);
    for (int i = 0; i < MAX; i++) {
      nums[i] = r.nextInt(MAX);
    }
    long begin = System.currentTimeMillis();
    sort(nums);
    long end = System.currentTimeMillis();
    System.out.println((end - begin)); // 以这个时间为标准，越小越好。
      }  public static int[] sort(int[] nums) {
    // 您的排序代码放在这里啦
  quickSort(nums, 0,100000-1);
    return nums;
  }
private static int partity(int array[],int first ,int last){
int s1last=first;
int start=first;
int poitle=array[first++];
int temp;
while(first-1<last){
if(poitle<=array[first]){

first++;
}
else{
temp=array[first];
array[first]=array[s1last+1];
array[++s1last]=temp;
first++;
}
}
if(s1last>=0){
temp=array[s1last];
array[s1last]=poitle;
array[start]=temp;}
return s1last;
}
public static void quickSort(int [] array,int first,int last ){
if(first<last){
int poite=partity(array, first, last);
quickSort(array,first,poite-1);
quickSort(array,poite+1,last);
}
}
}以前写的快速排序，
10万：15
100万：312
1000万:3734 有点慢哈

import java.util.Random;class T {
    public static void main(String[] args) {
        int MAX = 100000;
        int[] nums = new int[MAX];
        Random r = new Random(20080623);
        for (int i = 0; i < MAX; i++) {
            nums[i] = r.nextInt(MAX);
        }
        long begin = System.currentTimeMillis();
        sort(nums);
        long end = System.currentTimeMillis();
        System.out.println((end - begin)); // 以这个时间为标准，越小越好。
    }    public static int[] sort(int[] nums) {
        int size = nums.length;
        int tmp;
        int split1 = nums[0];
        int split2 = nums[0];
        int splitIndex1 = 0;
        int splitIndex2 = 100000;
        for (int i = 0; i < size; i++) {
            if (nums[i] < split1) {
                for (int j = i; j < splitIndex1; j++) {
                    if (nums[i] > nums[j]) {
                        tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        splitIndex1 = j;
                    }
                }
                split1 = nums[i];
            } else if (nums[i] > split2) {
                for (int j = splitIndex2; j < size; j++) {
                    if (nums[i] > nums[j]) {
                        tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        splitIndex2 = j;
                    }
                }
                split2 = nums[i];
            } else {
                for (int j = splitIndex1; j < splitIndex2; j++) {
                    if (nums[i] > nums[j]) {
                        tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                        splitIndex2 = j;
                    }
                }
                split2 = nums[i];
            }
        }
        return nums;
    }
}不知道这是什么排序方式......

[code=Java]    public static int[] sort(int[] nums)
    {
        quickSort(nums, 0, (int) nums.length - 1);
        return nums;
    }    // 快速排序方法
    public static void quickSort(int[] nums, int start, int end)
    {
        int lstart = start;
        int lend = end;        if (lstart >= lend)
            return;        boolean transfer = true;        while (lstart != lend)
        {
            if (nums[lstart] > nums[lend])
            {
                int temp = nums[lstart];
                nums[lstart] = nums[lend];
                nums[lend] = temp;
                transfer = (transfer == true) ? false : true;
            }            if (transfer)
                lend--;
            else
                lstart++;        }        lstart--;
        lend++;
        quickSort(nums, start, lstart);
        quickSort(nums, lend, end);
    }
[code]

public static int[] sort(int[] nums)
    {
        quickSort(nums, 0, (int) nums.length - 1);
        return nums;
    }     // 快速排序方法
    public static void quickSort(int[] nums, int start, int end)
    {
        int lstart = start;
        int lend = end;         if (lstart >= lend)
            return;         boolean transfer = true;         while (lstart != lend)
        {
            if (nums[lstart] > nums[lend])
            {
                int temp = nums[lstart];
                nums[lstart] = nums[lend];
                nums[lend] = temp;
                transfer = (transfer == true) ? false : true;
            }             if (transfer)
                lend--;
            else
                lstart++;         }         lstart--;
        lend++;
        quickSort(nums, start, lstart);
        quickSort(nums, lend, end);
    }

如果是整数的情况下，最快的是基数排序，平均时间是O(n)，但它是用空间换时间，要耗费大量空间用于存储数组在一般排序的情况下，最好的就是快排了，平均时间是O(nlgn)冒泡法大约是O(n2)堆排序如果没记错的话也应该是O(nlgn)可能前面的系数有细微不同吧～

import java.util.Random;public class T { public static void main(String[] args) {
final int MAX = 1000000; //1百万
final Random RND = new Random(20080623);
int[] nums = new int[MAX];
for (int i = 0; i < nums.length; /*nothing*/) {
nums[i++] = RND.nextInt(MAX);
}
long begin = System.currentTimeMillis();
sort(nums);
long end = System.currentTimeMillis();
System.out.println((end - begin)); //以这个时间为标准，越小越好。
} public static int[] sort(int[] nums) {
//您的排序代码放在这里啦
quickSort(nums, 0, nums.length - 1);
return nums;
} private static void quickSort(int[] a, int lo, int hi) {
int lot = lo;
int hit = hi;
int mid;
if (hi > lo) {
mid = a[(lo + hi) / 2];
while (lot <= hit) {
while ((lot < hi) && (a[lot] < mid)) ++lot;
while ((hit > lo) && (a[hit] > mid)) --hit;
if (lot <= hit) {
int t = a[lot];
a[lot] = a[hit];
a[hit] = t;
++lot;
--hit;
}
}
if (lo < hit) quickSort(a, lo, hit);
if (lot < hi) quickSort(a, lot, hi);
}
}}

堆排序算法的实现 // 堆排序的主体部分
static void HeapSort(int[] a) {
int i;
int n = a.length;
for (i = n - 1; i >= 0; i--) {
check(a, i, n - 1);
}
for (i = n - 1; i >= 0; i--) {
swap(a, 0, i);
check(a, 0, i - 1);
}
}

// 判断部分
static void check(int[] a, int parent, int high) {
int left = 2 * parent + 1;
int right = left + 1;
int temp = parent; if (left <= high && a[left] > a[temp]) {
temp = left;
}
if (right <= high && a[right] > a[temp]) {
temp = right;
}
if (temp != parent) {
swap(a, parent, temp);
check(a, temp, high);
}
} // 数组上，位于x1和x2的值交换
static void swap(int[] a, int x1, int x2) {
int temp = a[x1];
a[x1] = a[x2];
a[x2] = temp;
}
本机上的运行结果：
int MAX = 100000; 32
int MAX = 1000000; 625

    public static int[] sort(int[] nums) {
        //您的排序代码放在这里啦
        int[] tnums1 = new int[nums.length];
        int[] tnums2 = new int[nums.length];
        Arrays.fill(tnums1, 0);
        for(int i =0;i<nums.length;i++){
            tnums1[nums[i]] = tnums1[nums[i]] + 1;
        }

        int t2 = 0;
        for(int i =0;i<tnums1.length;i++){
            for(int j = 0;j<tnums1[i];j++){
                tnums2[t2++] = i;
            }
        }
        return tnums2;
    }

#include <algorithm>
#include <vector>
vector<int> _sort(vector<int>& nums)
{
        //您的排序代码放在这里啦
        sort(nums.begin(),nums.end());
        return nums;
}

public static int[] sort(int[] nums) {
        //您的排序代码放在这里啦
        int[] tnums1 = new int[nums.length];
        int[] tnums2 = new int[nums.length];
        for(int i =0;i<nums.length;i++){
            tnums1[nums[i]] = tnums1[nums[i]] + 1;
        }

        int t2 = 0;
        for(int i =0;i<tnums1.length;i++){
            for(int j = 0;j<tnums1[i];j++){
                tnums2[t2++] = i;
            }
        }
        return tnums2;
    }

talent_marquis
zhangdehai 你们的代码是错误的，排序结果错误

到目前为止，是 sort_john_sheep 的算法最快！

目前的排名如下，第一个是用户名，第二个数据是纳秒数。后面是验证排序结果正确的标志    sort_john_sheep=       51516045 1 1176 23276 67593 999999
    sort_joneyonly3=      148341479 1 1176 23276 67593 999999
      sort_preferme=      191153065 1 1176 23276 67593 999999
     qSor_hmsuccess=      195229282 1 1176 23276 67593 999999
        sort_B_Lee2=      195867911 1 1176 23276 67593 999999
     sort_J_Factory=      196162920 1 1176 23276 67593 999999
        sort_sagezk=      203846858 1 1176 23276 67593 999999
    sort_OXFORD_216=      210123353 1 1173 26018 68135 999999
           sort_JDK=      217118935 1 1176 23276 67593 999999
    sort_joneyonly2=      269188962 1 1176 23276 67593 999999
   quickSort_jdlsfl=      269909443 1 1176 23276 67593 999999
  sort_geyunfei_hit=      292163949 1 1176 23276 67593 999999
     sort_joneyonly=      357829556 1 1176 23276 67593 999999
sort_aunty_flybird=      427363534 1 1176 23276 67593 999999

下面是1000万数据的结果，内存设置为512m
    sort_john_sheep=      775251604 1 1203 23591 67888 9999998
    sort_joneyonly3=     1704502387 1 1203 23591 67888 9999998
      sort_preferme=     2122702187 1 1203 23591 67888 9999998
     qSor_hmsuccess=     2222824968 1 1203 23591 67888 9999998
     sort_J_Factory=     2232651915 1 1203 23591 67888 9999998
        sort_B_Lee2=     2260457963 1 1203 23591 67888 9999998
        sort_sagezk=     2303545283 1 1203 23591 67888 9999998
    sort_OXFORD_216=     2323731648 1 1274 31302 70596 9999998
           sort_JDK=     2400988673 1 1203 23591 67888 9999998
    sort_joneyonly2=     2964884085 1 1203 23591 67888 9999998
   quickSort_jdlsfl=     3121386098 1 1203 23591 67888 9999998
     sort_joneyonly=     6641849733 1 1203 23591 67888 9999998
sort_aunty_flybird=     9160276795 1 1203 23591 67888 9999998
  sort_geyunfei_hit=    31031545908 1 1203 23591 67888 9999998

看了一下john_sheep的代码，比我的精巧，主要在变量max的使用上。佩服！

    public static void main(String[] args) {        final int MAX = 100000; // 5百万
        final Random RND = new Random(20080623);
        int[] nums = new int[MAX];
        for (int i = 0; i < nums.length; /* nothing */) {
            nums[i++] = RND.nextInt(MAX);
        }
        long begin = System.currentTimeMillis();
        // sort(nums);
        System.out.println(Arrays.toString(sort(nums)).equals(Arrays.toString(mysort(nums))));        // Arrays.sort(nums);
        // System.out.println(Arrays.toString(nums));
        // System.out.println(Arrays.toString(mysort(nums)));
        long end = System.currentTimeMillis();
        System.out.println((end - begin)); // 以这个时间为标准，越小越好。
    }    public static int[] mysort(int[] nums) {        // 您的排序代码放在这里啦
        int[] tnums1 = new int[nums.length];
        int[] tnums2 = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tnums1[nums[i]] = tnums1[nums[i]] + 1;
        }        int t2 = 0;
        for (int i = 0; i < tnums1.length; i++) {
            for (int j = 0; j < tnums1[i]; j++) {
                tnums2[t2++] = i;
            }
        }
        return tnums2;
    }    // 这个是john_sheep的
    public static int[] sort(int[] nums) {        int max = getMax(nums) + 1;
        int[] temp = new int[max];
        for (int i : nums) {
            temp[i]++;
        }
        int pos = 0;
        for (int i = 0; i < max; i++) {
            if (temp[i] > 0) {
                for (int l = 0; l < temp[i]; l++)
                    nums[pos++] = i;
            }
        }
        return nums;
    }

public static int[] sort(int[] nums)
{
int max = getMax(nums) + 1;
int[] temp = new int[max];
for (int i =0;i<nums.length;i++)
{
temp[i]++;
}
int pos = 0;
for (int i = 0; i < max; i++)
{
if (temp[i] > 0)
{
for (int l = 0; l < temp[i]; l++)
nums[pos++] = i;
}
}
return nums;
} private static int getMax(int[] nums)
{
int max = 0;
for (int i = 0 ;i<nums.length;i++)
{
if (i > max)
{
max = i;
}
}
return max;
}
要想快，必须要用for( xxx;xxx;xxx){}

MAX 改一千万，看谁不 OutOfMemoryError。

package test;import java.util.Arrays;
import java.util.Random;public class T {    public static void main(String[] args) {        final int MAX = 1000000; // 1百万
        final Random RND = new Random(20080623);
        int[] nums = new int[MAX];
        for (int i = 0; i < nums.length; /* nothing */) {
            nums[i++] = RND.nextInt(MAX);
        }


        long begin = System.currentTimeMillis();
        mysort(nums);
        long end = System.currentTimeMillis();
        System.out.println((end - begin)); // 以这个时间为标准，越小越好。

        //判断结果
        int[] nums2 = mysort(nums);
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums2).equals(Arrays.toString(nums)));

    }    public static int[] mysort(int[] nums) {        // 您的排序代码放在这里啦
        int[] tnums1 = new int[nums.length];
        int[] tnums2 = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tnums1[nums[i]] = tnums1[nums[i]] + 1;
        }        int t2 = 0;
        for (int i = 0; i < tnums1.length; i++) {
            for (int j = 0; j < tnums1[i]; j++) {
                tnums2[t2++] = i;
            }
        }
        return tnums2;
    }
}
我本机用500万测的 1G内存。那里错了啊真迷糊

package temporary;import java.util.Random;public class Sort {

    static int MAX = 1000000;
    static  int[] _data = new int[MAX];
    public static void main(String[] args) {

    Random r = new Random(20080623);
    for (int i = 0; i < MAX; i++) {
     _data[i] = r.nextInt(MAX);
    }
    long begin = System.nanoTime();
    _data = sort(_data);
    long end = System.nanoTime();
    System.out.println("consume time is: "+(end - begin)); // 以这个时间为标准，越小越好。

}

    static int[] countSort(int n)
    {
     int i;
     int k = getMax();

     int[] c = new int [k+1];
     int[] b = new int [n];
     for(i = 0; i < n; i++)
          c[_data[i]]++;
     for(i = 1; i<=k; i++)
             c[i]+=c[i-1];
     for(i = n - 1; i >= 0; i--)
     {
          b[c[_data[i]]-1] = _data[i];
          c[_data[i]]--;
     }
     return b;
    }    static int getMax()    {
        int max = 0;
        for( int i : _data ){
            if( i > max ){
                max = i;
            }
        }
        return max;
    } }
这是我给的计数排序，我目前所能力及的最快的了

调试易

【竞赛】排序算法的最快实现

解决方案 »