黑马程序员技术交流社区

标题: Java中各种排序算法，你都知道哪些？ [打印本页]

作者: 曾欢欢 时间: 2014-5-5 17:45
标题: Java中各种排序算法，你都知道哪些？
本帖最后由曾欢欢于 2014-5-7 09:08 编辑

正在学习Java算法，快来添砖加瓦吧

作者: 程序爱好者 时间: 2014-5-5 18:45
001       //插入排序:
002
003       package org.rut.util.algorithm.support;
004
005       import org.rut.util.algorithm.SortUtil;
006       /**
007       * @author treeroot
008       * @since 2006-2-2
009       * @version 1.0
010       */
011       public class InsertSort implements SortUtil.Sort{
012
013          /** (non-Javadoc)
014          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
015          */
016          public void sort(int[] data) {
017             int temp;
018             for(int i=1;i<data.length;i++){
019                   for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
020                      SortUtil.swap(data,j,j-1);
021                   }
022             }
023          }
024
025       }
026       //冒泡排序:
027
028
029       for(var i=0; i<arr.length; i++) {
030          for(var j=i+1; j<=arr.length-1; j++) {
031             if(eval(arr[i]) < eval(arr[j])) {
032                   temp = arr[i];
033                   arr[i] = arr[j];
034                   arr[j] = temp;
035             }
036          }
037       }
038
039
040
041       package org.rut.util.algorithm.support;
042
043       import org.rut.util.algorithm.SortUtil;
044
045       /**
046       * @author treeroot
047       * @since 2006-2-2
048       * @version 1.0
049       */
050       public class BubbleSort implements SortUtil.Sort{
051
052          /** (non-Javadoc)
053          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
054          */
055          public void sort(int[] data) {
056             int temp;
057             for(int i=0;i<data.length;i++){
058                   for(int j=data.length-1;j>i;j--){
059                      if(data[j]<data[j-1]){
060                         SortUtil.swap(data,j,j-1);
061                      }
062                   }
063             }
064          }
065
066       }
067
068       //选择排序:
069
070       package org.rut.util.algorithm.support;
071
072       import org.rut.util.algorithm.SortUtil;
073
074       /**
075       * @author treeroot
076       * @since 2006-2-2
077       * @version 1.0
078       */
079       public class SelectionSort implements SortUtil.Sort {
080
081          /**
082          * (non-Javadoc)
083          *
084          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
085          */
086          public void sort(int[] data) {
087             int temp;
088             for (int i = 0; i < data.length; i++) {
089                   int lowIndex = i;
090                   for (int j = data.length - 1; j > i; j--) {
091                      if (data[j] < data[lowIndex]) {
092                         lowIndex = j;
093                      }
094                   }
095                   SortUtil.swap(data,i,lowIndex);
096             }
097          }
098
099       }
100
101       //Shell排序:
102
103       package org.rut.util.algorithm.support;
104
105       import org.rut.util.algorithm.SortUtil;
106
107       /**
108       * @author treeroot
109       * @since 2006-2-2
110       * @version 1.0
111       */
112       public class ShellSort implements SortUtil.Sort{
113
114          /** (non-Javadoc)
115          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
116          */
117          public void sort(int[] data) {
118             for(int i=data.length/2;i>2;i/=2){
119                   for(int j=0;j<i;j++){
120                      insertSort(data,j,i);
121                   }
122             }
123             insertSort(data,0,1);
124          }
125
126          /**
127          * @param data
128          * @param j
129          * @param i
130          */
131          private void insertSort(int[] data, int start, int inc) {
132             int temp;
133             for(int i=start+inc;i<data.length;i+=inc){
134                   for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
135                      SortUtil.swap(data,j,j-inc);
136                   }
137             }
138          }
139
140       }
141
142       //快速排序:
143
144       package org.rut.util.algorithm.support;
145
146       import org.rut.util.algorithm.SortUtil;
147
148       /**
149       * @author treeroot
150       * @since 2006-2-2
151       * @version 1.0
152       */
153       public class QuickSort implements SortUtil.Sort{
154
155          /** (non-Javadoc)
156          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
157          */
158          public void sort(int[] data) {
159             quickSort(data,0,data.length-1);
160          }
161          private void quickSort(int[] data,int i,int j){
162             int pivotIndex=(i+j)/2;
163             //swap
164             SortUtil.swap(data,pivotIndex,j);
165
166             int k=partition(data,i-1,j,data[j]);
167             SortUtil.swap(data,k,j);
168             if((k-i)>1) quickSort(data,i,k-1);
169             if((j-k)>1) quickSort(data,k+1,j);
170
171          }
172          /**
173          * @param data
174          * @param i
175          * @param j
176          * @return
177          */
178          private int partition(int[] data, int l, int r,int pivot) {
179             do{
180                while(data[++l]<pivot);
181                while((r!=0)&&data[--r]>pivot);
182                SortUtil.swap(data,l,r);
183             }
184             while(l<r);
185             SortUtil.swap(data,l,r);
186             return l;
187          }
188
189       }
190       //改进后的快速排序:
191
192       package org.rut.util.algorithm.support;
193
194       import org.rut.util.algorithm.SortUtil;
195
196       /**
197       * @author treeroot
198       * @since 2006-2-2
199       * @version 1.0
200       */
201       public class ImprovedQuickSort implements SortUtil.Sort {
202
203          private static int MAX_STACK_SIZE=4096;
204          private static int THRESHOLD=10;
205          /** (non-Javadoc)
206          * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
207          */
208          public void sort(int[] data) {
209             int[] stack=new int[MAX_STACK_SIZE];
210
211             int top=-1;
212             int pivot;
213             int pivotIndex,l,r;
214
215             stack[++top]=0;
216             stack[++top]=data.length-1;
217
218             while(top>0){
219                   int j=stack[top--];
220                   int i=stack[top--];
221
222                   pivotIndex=(i+j)/2;
223                   pivot=data[pivotIndex];
224
225                   SortUtil.swap(data,pivotIndex,j);
226
227                   //partition
228                   l=i-1;
229                   r=j;
230                   do{
231                      while(data[++l]<pivot);
232                      while((r!=0)&&(data[--r]>pivot));
233                      SortUtil.swap(data,l,r);
234                   }
235                   while(l<r);
236                   SortUtil.swap(data,l,r);
237                   SortUtil.swap(data,l,j);
238
239                   if((l-i)>THRESHOLD){
240                      stack[++top]=i;
241                      stack[++top]=l-1;
242                   }
243                   if((j-l)>THRESHOLD){
244                      stack[++top]=l+1;
245                      stack[++top]=j;
246                   }
247
248             }
249             //new InsertSort().sort(data);
250             insertSort(data);
251          }
252          /**
253          * @param data
254          */
255          private void insertSort(int[] data) {
256             int temp;
257             for(int i=1;i<data.length;i++){
258                   for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
259                      SortUtil.swap(data,j,j-1);
260                   }
261             }
262          }
263
264       }

作者: 来男. 时间: 2014-5-6 00:59
我觉得只要掌握如下算法就足够了，是视频内容也是重要的基础！

总结：

import java util.*;//引入util包
class AllOfCase
{
public static void main(String[] args)
{
  int[] arr={2,34,5,6,7,556};

  //基础1 数值换位
  public static void swap(int[] arr,int a ,int b)
  {
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
  }

  //基础2 遍历数组
  public static void printArr(int[] arr)
  {
System.out.print("[");
for(int x=0;x<arr.length;x++)
{
if(x!=arr.length-1)
   System.out.print(arr[x]+", ");
else
   System.out.println(arr[x]+"]");
}
  }

  //最值(1)
  public static int Max_1(int[] arr)
  {
int max=arr[0];//设最大值
for(int x=1;x<arr.length;x++)
{
if(arr[x]>max)//若后面比最大值还大，则取它，取最小值则小于号
max=arr[x];
}
return max;//返回最值
  }

  //最值(2)
  public static int Max_2(int[] arr)
  {
int max=0;//暂且设最大值角标为0
for(int x=1;x<arr.length;x++)
{
if(arr[x]>arr[max])//同上
max=x;//返回最大值角标
}
return arr[max];//返回最值
  }

  //选择排序
  public static void selSort(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);
   }
}
}
  }

  //冒泡排序
  public static void bubSort(int[] arr)
  {
for(int x=0;x<arr.length-1;x++)
{
for(int y=0;y<arr.length-x-1;y++)//-x让每次比较的元素减少，-1避免角标越界
{
   if(arr[y]>arr[y+1])
   {
   swap(arr,y,y+1);
   }
}
}
  }

  //普通查找
  public static int getKey(int[] arr,int key)
  {
for(int x=0;x<arr.length;x++)
{
if(arr[x]==key)//找到对应值后返回下标
return x;
}
return -1;
  }

  //二分查找(1)
  public static int halKey_1(int[] arr,int key)
  {
int max=arr.length-1,mid=(max+min)/2,min=0;
while(arr[mid]!key)
{
if(key>arr[mid])
   min=mid+1;//右移1位
else if(key<arr[mid])
   max=mid-1;//左移1位
if(min>max)
   return -1;
mid=(max+min)/2;//取中
}
reutrun mid;
  }

  //二分查找(2)
  public static int halKey_2(int[] arr,int key)
  {
int max=arr.length-1,min=0,mid;
while(min<=max)
{
mid=(max+min)>>1;//右移1就是除2
if(key>arr[mid])
   min=mid+1;//右移1位
else if(key<arr[mid])
   max=mid-1;//左移1位
else
   return mid;
}
reutrun -min-1;
  }

  //反转
  public static void revArr(int[] arr)
  {
for(intx =0,y=arr.length-1;x<y;x++,y--)
{
swap(arr,x,y);
}
  }
}
}

作者: 曾欢欢 时间: 2014-5-6 10:57

来男. 发表于 2014-5-6 00:59
我觉得只要掌握如下算法就足够了，是视频内容也是重要的基础！

总结：

想提升一下自己，学习视频其他算法

作者: 曾欢欢 时间: 2014-5-6 11:04

程序爱好者发表于 2014-5-5 18:45
001       //插入排序:
002
003       package org.rut.util.algorithm.support;

很好，学习中

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

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