A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© Bad_Boy 中级黑马   /  2013-9-21 16:35  /  1918 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 Bad_Boy 于 2013-9-22 00:00 编辑

数组的快速排序方法?

评分

参与人数 1技术分 +1 收起 理由
EYE_SEE_YOU + 1

查看全部评分

5 个回复

倒序浏览
本帖最后由 常在河边走_ 于 2013-9-21 16:43 编辑

/*
* 快速排序:
* 一趟快速排序的算法是:   
* 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;   
* 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];   
* 3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--),
* 找到第一个小于key的值A[j],A与A[j]交换;   
* 4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++),
* 找到第一个大于key的A,A与A[j]交换;   
* 5)重复第3、4、5步,直到 I=J;
* (3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。
* 找到并交换的时候i, j指针位置不变。
* 另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。)
*/
public class QuickSort {
        public static void sort(int[] data) {
                quickSort(data, 0, data.length - 1);
        }

        private static void quickSort(int[] data, int i, int j) {
                int pivotIndex = (i + j) / 2;
                // swap
                SortTest.swap(data, pivotIndex, j);

                int k = partition(data, i - 1, j, data[j]);
                SortTest.swap(data, k, j);
                if ((k - i) > 1)
                        quickSort(data, i, k - 1);
                if ((j - k) > 1)
                        quickSort(data, k + 1, j);

        }


评分

参与人数 1技术分 +1 收起 理由
EYE_SEE_YOU + 1

查看全部评分

回复 使用道具 举报
快排(用递归实现)
  1. public class MySort
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr = {1,6,7,5,3,5,8,9,7,56};
  6.                
  7.                
  8.                 QuickSort.Sort(arr, 0, arr.length-1);
  9.                
  10.                
  11.                 for (int i = 0; i < arr.length; ++i)
  12.                 {
  13.                         System.out.println(arr[i]);
  14.                 }
  15.         }
  16. }

  17. class QuickSort
  18. {
  19.         public static  void Sort(int arr[], int low, int high)
  20.         {
  21.                 int pos = 0;
  22.                
  23.                 if (low < high)
  24.                 {
  25.                         pos = FindPos(arr, low, high);
  26.                         Sort(arr, low, pos-1);
  27.                         Sort(arr, pos+1, high);
  28.                 }
  29.         }
  30.        
  31.         public static  int FindPos(int arr[], int low, int high)
  32.         {
  33.                 int val = arr[low];
  34.                 while (low < high)
  35.                 {
  36.                         while (low < high && arr[high] >= val)
  37.                                 --high;
  38.                         arr[low] = arr[high];
  39.                        
  40.                         while (low < high && arr[low] <= val)
  41.                                 ++low;
  42.                         arr[high] = arr[low];
  43.                 }
  44.                 arr[low] = val;
  45.                 return low;
  46.         }
  47. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
EYE_SEE_YOU + 1

查看全部评分

回复 使用道具 举报
class PaiXu
{
public static void main(String[]args)
{
int []arr={3,5,8,1,4,2,9,2}
seletsort(arr);
bubblesort(arr);
}
/**
给int数组选择排序
*/
public static void selectsort(int[]arr)
{
for (int x=0;x<arr.length-1;  x++)
{
  for (int y=x+1;y<arr.length ;y++ )
  {
   if (arr[x]>arr[y])
   {
    swap(arr,x,y);
   }
  }
}
}
/**
给int数组进行冒泡排序
*/
public static void bubblesort(int[]arr)
{
for (intx=0;x<arr.length-1 ;x++ )
{
  for (int y=0;y<arr.length-x-1 ;y++ )
  {
   if (arr[y]>arr[y+1])
   {
    swap(arr,y,y+1);
   }
  }
}
}
/**
给数组中的元素进行位置置换
*/
public static void swap(int[]arr,int a,int b)//换位操作
{
int temp =arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}

评分

参与人数 1技术分 +1 收起 理由
EYE_SEE_YOU + 1

查看全部评分

回复 使用道具 举报

public class QuickSort {
     private void sort(int[] data, int left, int right) {
         int i = left;
         int j = right;
         int middle = data[(left + right) / 2];
         do{
             while(data[i] < middle && i < right) i ++;
             while(data[j] > middle && j > left) j --;
             if(i <= j) {
                 int itemp = data[i];
                 data[i] = data[j];
                 data[j] = itemp;  
                i ++;
                 j --;
             }
         } while(i <= j);

         if(left < j) sort(data, left, j);
     
         if(right > i) sort(data, i, right);
     }
     
     public void sort(int[] data) {
         sort(data, 0, data.length - 1);
     }

    public static void main(String[] args) {
         QuickSort sort = new QuickSort();
         int[] data = {1, 2, 5, 7, 9, 3, 2, 0, 10, 4};
         sort.sort(data);
         for(int i = 0; i < data.length; i ++) {
             System.out.print(data[i] + "  ");
         }
     }
}









回复 使用道具 举报
public class QuickSortTset {

  public static void main(String[] args) {

  Random r=new Random();

  int[] arr=new int[10];

  for(int i=0;i<arr.length;i++){ //随机生成10个排序数

  Integer a =r.nextInt(100);

  arr[i]= a;

  System.out.print(arr[i]+" ");

  }

  System.out.println();

  int left=0;

  int right=arr.length-1;

  Sort(arr,left,right);

  for(int i=0;i<arr.length;i++){

  System.out.print(arr[i]+"  ");

  }

  System.out.println();

  }

  public static int[] Sort(int[] arr, int left, int right){

  int middle,strTemp;

  int i = left;

  int j = right;

  middle = arr[(left+right)/2];

  do{

  while((arr[i]<middle) && (i<right))

  i++;

  while((arr[j]>middle) && (j>left))

  j--;

  if(i<=j){

  strTemp = arr[i];

  arr[i] = arr[j];

  arr[j] = strTemp;

  i++;

  j--;

  }

  for(int k=0;k<arr.length;k++){

  System.out.print(arr[k]+"  ");

  }

  System.out.println();

  }while(i<j);//如果两边扫描的下标交错,完成一次排序

  if(left<j)

  Sort(arr,left,j); //递归调用

  if(right>i)

  Sort(arr,i,right); //递归调用

  return arr;

  }

  }

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马