黑马程序员技术交流社区

标题: 刚刚学到排序，希望大神系统的给点归纳 [打印本页]

---

作者: 805948289    时间: 2015-3-13 23:08
标题: 刚刚学到排序，希望大神系统的给点归纳
排序都有哪几种方法？用JAVA实现一个快速排序。

---

作者: 我只适合被遗忘    时间: 2015-3-13 23:08
本人只研究过冒泡排序、选择排序和快速排序，下面是快速排序的代码：

public class QuickSort {
/**
* 快速排序
* @param strDate
* @param left
* @param right
*/
public void quickSort(String[] strDate,int left,int right){
String middle,tempDate;
int i,j;
i=left;
j=right;
middle=strDate[(i+j)/2];
do{
while(strDate[i].compareTo(middle)<0&& i<right)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>left)
j--; //找出右边比中间值小的数
if(i<=j){ //将左边大的数和右边小的数进行替换
tempDate=strDate[i];
strDate[i]=strDate[j];
strDate[j]=tempDate;
i++;
j--;
}
}while(i<=j); //当两者交错时停止

if(i<right){
quickSort(strDate,i,right);//从
}
if(j>left){
quickSort(strDate,left,j);
}
}
/**
  * @param args
  */
public static void main(String[] args){
String[] strVoid=new String[]{"11","66","22","0","55","22","0","32"};
QuickSort sort=new QuickSort();
sort.quickSort(strVoid,0,strVoid.length-1);
for(int i=0;i<strVoid.length;i++){
System.out.println(strVoid[i]+" ");
}
}


}


classpath  public private static  extends  interface  abstract implements  version   author
double   binary   hex  count  salary   random scanner  break  defalut  function  method  result
compare pointer exception error     thread  index  bound  sort  select  bubble change
search transition object claas me     package

---

作者: as604049322    时间: 2015-3-14 00:10
花了近21个小时的时间总算把各种排序算法弄懂了
http://bbs.itheima.com/thread-156588-1-1.html
(出处: 黑马程序员IT技术论坛)

---

作者: 梅西    时间: 2015-3-14 00:25
插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）
public class QuickSort {

/**
  * 快速排序
  *
  * @param strDate
  * @param left
  * @param right
  */
public void quickSort(String[] strDate, int left, int right) {
  String middle;
  String tempDate;
  int i, j;
  i = left;
  j = right;
  middle = strDate[(i + j) / 2];
  do {
   while (strDate[i].compareTo(middle) < 0 && i < right)
    i++; // 找出左边比中间值大的数
   while (strDate[j].compareTo(middle) > 0 && j > left)
    j--; // 找出右边比中间值小的数
   if (i <= j) { // 将左边大的数和右边小的数进行替换
    tempDate = strDate[i];
    strDate[i] = strDate[j];
    strDate[j] = tempDate;
    i++;
    j--;
   }
  } while (i <= j); // 当两者交错时停止

  if (i < right) {
   quickSort(strDate, i, right);
  }
  if (j > left) {
   quickSort(strDate, left, j);
  }
}

/**
  * @param args
  */
public static void main(String[] args) {
  String[] strVoid = new String[] { "11", "66", "22", "0", "55", "22",
    "0", "32" };
  QuickSort sort = new QuickSort();
  sort.quickSort(strVoid, 0, strVoid.length - 1);
  for (int i = 0; i < strVoid.length; i++) {
   System.out.println(strVoid[i] + " ");
  }
}

}

}

---

作者: 独孤忆    时间: 2015-3-14 01:05
楼主是做什么的？需要这么深入的研究排序？

---

作者: gaizuojia    时间: 2015-3-14 09:47

1. public int getMiddle(Integer[] list, int low, int high) {
   
2.                 int tmp = list[low];    //数组的第一个作为中轴
   
3.                 while (low < high) {
   
4.                         while (low < high && list[high] > tmp) {
   
5.                                 high--;
   
6.                         }
   
7.                         list[low] = list[high];   //比中轴小的记录移到低端
   
8.                         while (low < high && list[low] < tmp) {
   
9.                                 low++;
   
10.                         }
    
11.                         list[high] = list[low];   //比中轴大的记录移到高端
    
12.                 }
    
13.                 list[low] = tmp;              //中轴记录到尾
    
14.                 return low;                   //返回中轴的位置
    
15.         }

复制代码

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。
下面是分治排序法代码

1. public void _quickSort(Integer[] list, int low, int high) {
   
2.                 if (low < high) {
   
3.                         int middle = getMiddle(list, low, high);  //将list数组进行一分为二
   
4.                         _quickSort(list, low, middle - 1);        //对低字表进行递归排序
   
5.                         _quickSort(list, middle + 1, high);       //对高字表进行递归排序
   
6.                 }
   
7.         }
   

复制代码

这样整个就是一次快速排序。楼主采纳，谢谢！

---

作者: welfsen    时间: 2015-3-14 09:52
排序方法一般都就那几种。像冒泡排序，直接插入排序，快速排序，简单选择排序，希尔排序，堆排序。
package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

public class BubbleSort implements SortUtil.Sort{

    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for(int i=0;i<data.length;i++){
            for(int j=data.length-1;j>i;j–){
                if(data[j]<data[j-1]){
                    SortUtil.swap(data,j,j-1);
                }
            }
        }
    }

}

---

作者: lijifeng    时间: 2015-3-14 11:48
排序算法是数据结构的东西 和语言是没关系的
冒泡：



Java代码
1.public class BubbleSort {  
2.    public static void bubbleSort(int[] array) {  
3.        int length = array.length - 1;  
4.        for (int out = length; out > 0; out--) {  
5.            for (int in = 0; in < out; in++) {  
6.                if (array[in] > array[in + 1]) {  
7.                    int s = array[in];  
8.                    array[in] = array[in + 1];  
9.                    array[in + 1] = s;  
10.                }  
11.            }  
12.        }  
13.    }  
14.  
15.}  


插入：


Java代码
1.public class InsertSort {  
2.    public static void sort(int[]array){  
3.        int length=array.length;  
4.        for(int out=1;out<length;out++){  
5.            int temp=array[out];  
6.            int in=out;  
7.            while(in>0&&array[in-1]>temp){  
8.                array[in]=array[in-1];  
9.                --in;  
10.            }  
11.            array[in]=temp;  
12.        }  
13.    }  
14.}  


选择：


Java代码
1.public class SelectSort {  
2.    public static void sort(int[]array){  
3.        for(int out=0;out<array.length-1;out++){  
4.            int min=out;  
5.            for(int in=out+1;in<array.length;in++){  
6.                if(array[in]<array[min]){  
7.                    min=in;  
8.                }  
9.            }  
10.            int t =array[out];  
11.            array[out]=array[min];  
12.            array[min]=t;  
13.        }  
14.    }  
15.}  


希尔：


Java代码
1.public class SheelSort {  
2.    private int[] hs;  
3.  
4.    private int[] a;  
5.      
6.    public void sort(){  
7.        for(int h:hs){  
8.            for(int i=h;i<a.length;i++){  
9.                int in=i;  
10.                int inValue=a[i];  
11.                while(in-h>-1&&a[in-h]>inValue){  
12.                    a[in]=a[in-h];  
13.                    in=in-h;  
14.                }  
15.                a[in]=inValue;  
16.            }  
17.        }  
18.    }  
19.      
20.  
21.    public int[] getHs() {  
22.        return hs;  
23.    }  
24.  
25.    public void setHs(int[] hs) {  
26.        this.hs = hs;  
27.    }  
28.  
29.    public int[] getA() {  
30.        return a;  
31.    }  
32.  
33.    public void setA(int[] a) {  
34.        this.a = a;  
35.    }  
36.}  



快速：


Java代码
1.public class SpeedSort {  
2.    private int[] a;  
3.  
4.    public void sort() {  
5.        int begin = 0;  
6.        int end = a.length - 1;  
7.        quickSort(begin, end);  
8.        for (int i : a) {  
9.            System.out.print(i + " ");  
10.        }  
11.    }  
12.  
13.    private void quickSort(int begin, int end) {  
14.        if (begin >= end) {  
15.                  
16.        } else {  
17.            int pivot = a[end];  
18.            int result = getPivot(begin, end, pivot);  
19.            quickSort(begin, result - 1);  
20.            quickSort(result + 1, end);  
21.        }  
22.  
23.    }  
24.  
25.    private int getPivot(int begin, int end, int pivot) {  
26.        begin = begin - 1;  
27.        int o = end;  
28.        while (true) {  
29.            while (a[++begin] < pivot) {  
30.  
31.            }  
32.            while (end > 0 && a[--end] > pivot) {  
33.  
34.            }  
35.            if (begin >= end) {  
36.                break;  
37.            } else {  
38.                swap(begin, end);  
39.            }  
40.        }  
41.        swap(begin, o);  
42.        return begin;  
43.    }  
44.  
45.    private void swap(int begin, int end) {  
46.        int t = a[begin];  
47.        a[begin] = a[end];  
48.        a[end] = t;  
49.    }  
50.  
51.    public int[] getA() {  
52.        return a;  
53.    }  
54.  
55.    public void setA(int[] a) {  
56.        this.a = a;  
57.    }  
希望对你有些帮助

---

作者: 唐泉银    时间: 2015-3-14 23:18
哇 你这问题问的太深了吧

---

作者: 柯泉    时间: 2015-3-15 00:54
选择，冒泡，折半查找

---

作者: 柯泉    时间: 2015-3-15 00:55

柯泉 发表于 2015-3-15 00:54
选择，冒泡，折半查找

/*数组的选择排序
class Array1
{
        public static void main(String []args)
        {
                int []arr={3,6,5,4,9,7,8,0};
                sort(arr);
                printarray(arr);
        }

        public static void sort(int []arr)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr.length ;y++ )
                        {
                                if (arr[x]>arr[y])//大的在前 反着排
                                {
                                        int temp=arr[x];
                                           arr[x]=arr[y];
                                           arr[y]=temp;
                                }
                        }
                }
        }
       
        public static void printarray (int []arr)
        {
                for (int x=0;x<arr.length;x++         )
                {
                        System.out.print(arr[x]);
                }
               
        }
}
*/






/*//数组的冒泡排序
class Array1
{
        public static void main(String []args)
        {
                int []arr={3,6,5,4,9,7,8,0};
                sort(arr);
                printarray(arr);
        }

        public static void sort(int []arr)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr.length-x-1 ;y++ )
                        {
                                if (arr[y]>arr[y+1])//大的在前倒着排
                                {
                                        int temp=arr[y];
                                           arr[y]=arr[y+1];
                                           arr[y+1]=temp;
                                }
                        }
                }
        }
       
        public static void printarray (int []arr)
        {
                for (int x=0;x<arr.length;x++         )
                {
                        System.out.print(arr[x]);
                }
               
        }
}

*/



/*数组的折半查找 以key！=arr[mid]为主条件 while格式

折半查找数组必须是有序的

折半查找循环次数不明确，适合while结构，
for结构也可以运行是因为折半查找的次数小于arr.length

class Array1
{
        public static void main(String []args)
        {
                int []arr={0,1,2,3,4,5,6,7,8,9};
                int index=halfsearch(arr,8);
                System.out.println("index="+index);
        }



        public static int halfsearch(int []arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
                while (arr[mid]!=key)
                {
                        if (arr[mid]>key)
                        {
                                max=mid-1;
                        }
                        else if (arr[mid]<key)
                        {
                                min=mid+1;
                        }
                        if(min>max) return -1;
                        mid=(min+max)/2;
                }
                return mid;
        }
       
}
*/


/*
数组的折半查找 以ke!=arr[mid]为主条件 for格式

折半查找数组必须是有序的

折半查找循环次数不明确，适合while结构，
for结构也可以运行是因为折半查找的次数小于arr.length

class Array1
{
        public static void main(String []args)
        {
                int []arr={0,1,2,3,4,5,6,7,8,9};
                int index=halfsearch(arr,8);
                System.out.println("index="+index);
        }



        public static int halfsearch(int []arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
        for (int x=0;x<arr.length ; x++)
        {
                 
       
                if(arr[mid]!=key)
                {
                        if (arr[mid]>key)
                        {
                                max=mid-1;
                        }
                        else if (arr[mid]<key)
                        {
                                min=mid+1;//过程
                        }
                        if(min>max)  return -1;//结果
                        //为什么用if不用else
                        mid=(min+max)/2;
                }
                else return mid;
        }
       
        //为什么要有return:
        //定义返回值为int，
        //系统在最后查找时要确定有没有返回值要求类型
        //如果定义返回值为void，for循环内的int类型返回值将无法返回
        }
}
*/



/*数组的折半查找 以min<max为主条件 while格式

折半查找数组必须是有序的
class Array1
{
        public static void main(String []args)
        {
                int []arr={0,1,2,3,4,5,6,7,8,9};
                int index=halfsearch(arr,8);
                System.out.println("index="+index);
        }



        public static int halfsearch(int []arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
                while (min<=max)
                {
                        if (arr[mid]>key)
                        {
                                max=mid-1;
                        }
                        else if (arr[mid]<key)
                        {
                                min=mid+1;
                        }
                       
                        else        return mid;//结果
                        //相当于 if(arr[mid]=key) return mid;
                        mid=(min+max)/2;
                }
                return -1;
        }
       
}
*/



/*数组的折半查找  以mia<max为主条件 for格式

折半查找数组必须是有序的
class Array1
{
        public static void main(String []args)
        {
                int []arr={0,1,2,3,4,5,6,7,8,9};
                int index=halfsearch(arr,13);
                System.out.println("index="+index);
        }



        public static int halfsearch(int []arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
        for (int x=0;x<arr.length ; x++)
        {
                 
       
                if(min<max)
                {
                        if (arr[mid]>key)
                        {
                                max=mid-1;
                        }
                        else if (arr[mid]<key)
                        {
                                min=mid+1;//过程
                        }
                        if(min>max)  return -1;//结果
                        //为什么用if不用else
                        mid=(min+max)/2;
                }
                else  mid=mid;
        }
        return mid;//函数最终必须要有返回值，或者返回语句
        }
}
*/

---

作者: 致逝去的青春    时间: 2015-3-15 13:09
菜鸟目前只学了冒泡排序和折半排序这两种

---

作者: 高怀    时间: 2015-3-16 10:52
觉得大家好专业啊

---

作者: darewolf    时间: 2015-3-18 11:15
有内部排序和外部排序，内部排序中有基数，顺序，冒泡，快速，选择，希尔……

---

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

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