黑马程序员技术交流社区

标题: 求对数组快速排序的方法 [打印本页]

---

作者: Bad_Boy    时间: 2013-9-21 16:35
标题: 求对数组快速排序的方法


数组的快速排序方法？

---

作者: 常在河边走_    时间: 2013-9-21 16:40


/*
* 快速排序：
* 一趟快速排序的算法是： 　　
* 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);

        }

---

作者: 酱爆    时间: 2013-9-21 17:05
快排（用递归实现）

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

复制代码

---

作者: 咕咕猫    时间: 2013-9-21 17:19
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;
}
}

---

作者: 光脚丫的小白兔    时间: 2013-9-21 21:15

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] + "  ");
         }
     }
}

---

作者: doevents    时间: 2013-9-21 22:54
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;

　　}

　　}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2