[Java] 刚刚学到排序，希望大神系统的给点归纳

我只适合被遗忘

排序都有哪几种方法？用JAVA实现一个快速排序。

darewolf · darewolf

有内部排序和外部排序，内部排序中有基数，顺序，冒泡，快速，选择，希尔……

高怀 · 高怀

觉得大家好专业啊

致逝去的青春 · 致逝去的青春

菜鸟目前只学了冒泡排序和折半排序这两种

柯泉 · 柯泉

柯泉发表于 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;//函数最终必须要有返回值，或者返回语句
}
}
*/

柯泉 · 柯泉

选择，冒泡，折半查找

唐泉银 · 唐泉银

哇你这问题问的太深了吧

lijifeng · lijifeng

排序算法是数据结构的东西和语言是没关系的
冒泡：

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. }
希望对你有些帮助

welfsen · welfsen

排序方法一般都就那几种。像冒泡排序，直接插入排序，快速排序，简单选择排序，希尔排序，堆排序。
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);
            }
         }
      }
}

}

gaizuojia · gaizuojia

public int getMiddle(Integer[] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] > tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] < tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}

复制代码

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

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

复制代码

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

独孤忆 · 独孤忆

楼主是做什么的？需要这么深入的研究排序？

梅西 · 梅西

插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）
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] + " ");
  }
}

}

}

as604049322 · as604049322

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

我只适合被遗忘 · 我只适合被遗忘

本人只研究过冒泡排序、选择排序和快速排序，下面是快速排序的代码：

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

帐号		自动登录	找回密码
密码			加入黑马

[Java] 刚刚学到排序，希望大神系统的给点归纳

最佳答案

13 个回复

浏览过的版块

优秀作者