数据结构与算法:掌握基础的排序方法

发表时间: 2019-09-05 16:27

简单排序有三种,分别是冒泡排序、选择排序和插入排序。

首先自定义一些数据和方法,待会排序算法需要用到,都是用Java写的。

 public static int[] data= {77, 99, 44, 55, 22, 88, 11, 66, 33};  public static void main(String[] var) { display(); insertSort(); display(); }  public static void display () { //打印data[] for (int j=0; j<data.length; j++) { System.out.print(data[j] + " "); } System.out.println(""); } public static void swap (int one, int two) { //交换两个数据的位置 int temp = data[one]; data[one] = data[two]; data[two] = temp; }

冒泡排序

冒泡排序思想:

  1. 一些人站成一排,第一个与第二个比身高,哪个高的就站第二位;第二个与第三个比身高,哪个高的就站第三位......一直进行下去,最高的那个人就站到了最后一位。
  2. 再来一遍,第一个与第二个比身高,哪个高的就站第二位.......,一直进行到最后一个的前一个为止,因为最后一个已经确定下来了。这个过程一直进行下去,直到整排有序为止。
 private static void bubbleSort() { int out, in; for (out=data.length-1; out>0; out--) { for (in=0; in<out; in++) { if (data[in] > data[in+1]) { swap(in, in+1); } } } }

选择排序

选择排序思想:

  1. 一些人站成一排,从第一个开始,用小本子把这个人的位置和身高记下来,第二个人与小本子里的身高作比较,如果比它小,更新小本子的记录,小本子只记身高比较矮的。第三个再与小本子比较....一直进行下去,直到最后一个与小本子比较完。这样小本子里的记录就是最矮的那个人,把这个人与第一个交换一下位置就行了。
  2. 然后从第二个开始重复1步骤,直到整排有序。
 private static void selectionSort() { int left, right, temp; for (left=0; left<data.length-1; left++) { temp = left; for (right=left+1; right<data.length; right++) { if (data[right] < data[temp]) { temp = right; } } swap(left, temp); } }

插入排序

插入排序思想:

  1. 一些人站成一排是无序的,但是,只看第一个人(只有一个人)是有序的部分,后面那些人是无序的。先处理第二个人,把他叫出来,他的位置就空着。
  2. 一一比较第二个人和前面那些人的身高,如果比较矮,前面那个人就往后退一格,将他自己的位置空出来。如果比较高,那么被叫出来的那个就站在前面那个后面就行了。一直进行下去,直到他的位置确定下来之后,有序的部分就多加一人了。
  3. 再处理第三个人,与第二个处理过程一样,然后第四个、第五个....直到最后一个,这样有序部分一个一个增加,整排就有序了。
 private static void insertSort() { int in, out; for (out=1; out<data.length; out++) { int temp = data[out]; in = out-1; while (in>=0 && data[in]>temp) { data[in+1] = data[in]; in--; } data[in+1] = temp; } }

总结

我大二上学期学完这门课,现在都忘了七七八八了,上述简单的三种排序我都忘了怎么写了,得多练练手,争取一碰到这种排序,都能在3分钟之内完成。