疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

四种初级排序算法


 

   

  一、冒泡排序

  1.原理

  (1)比较相邻的元素。如果第一个比第二个大,就交换他们两个;

  (2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数;

  (3)针对所有的元素重复以上的步骤,除了最后一个;

  (4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  2.一个直接但是低效的实现

  复制代码

  public void sort(int[] array) {

  //外层循环从第0个元素遍历到倒数第二个元素,主要是用来控制内层循环的次数

  //因为外层循环每跑一次,最大的数就会到最后面

  for (int i = 0; i < array.length - 1; i++) {

  //内层循环,遍历数组的每一个数(每一趟遍历的数量都在减小,因为最后面的是不需要比较的)

  //如果前面的比后面的大,就交换这俩个数

  for (int j = 0; j < array.length - i - 1; j++) {

  if (array[j] > array[j+1]) {

  int temp = array[j+1];

  array[j+1] = array[j];

  array[j] =temp;

  }

  }

  }

  }

  复制代码

  3.优化版本(优化的地方是,如果遍历了一次,发现没有任何交换,那么说明已经排好序了,后面就可以不用排了)

  复制代码

  public void sort(int[] array) {

  boolean swaped;

  int n = array.length;

  do {

  swaped = false;

  for (int i = 1; i < n; i++) {

  if (array[i - 1] > array[i]) {

  //如果这趟有两个元素换过位置,那么是否排过序设置成true

  //一旦有某一趟没有任何两个元素换过位置,说明已经排好了,整个排序过程可以停止了

  int temp = array[i - 1];

  array[i - 1] = array[i];

  array[i] = temp;

  swaped = true;

  }

  }

  n--;

  } while (swaped);

  }

  复制代码

  二、选择排序

  1.原理:

  选择排序是对冒泡排序的改进,因为冒泡排序每次比较后都要互换两个元素位置,而互换的过程会有几次赋值,特别耗费时间。

  选择排序的思路:

  是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完

  2.一个简单的实现:

  复制代码

  public void sort(int[] array) {

  for (int i = 0; i < array.length; i++) {

  //找到最小元素的索引位置

  int minIndex = i;

  for (int j = i + 1; j < array.length; j++) {

  if (array[j] < array[minIndex]) {

  minIndex = j;

  }

  }

  int temp = array[i];

  array[i] = array[minIndex];

  array[minIndex] = temp;

  }

  }

  复制代码

  3.小结:

  选择排序因为每一次遍历都要从元素中选择最小的,所以每次都要遍历完整个数组,也是一个效率特别低的排序。

  三、插入排序

  1.原理:

  插入排序的原理和打牌的时候理牌比较像,就是每步将一个待排序的纪录,将其插入前面已经排序的序列的适当位置上,直到全部插入完为止。

  2.实现代码版本1:

  复制代码

  public void sort(int[] array) {

  for (int i = 1; i < array.length; i++) {

  //从外层循环的位置开始从前面找,如果j-1位置的数比j位置数大,那么交换

  for (int j = i; j > 0 ; j--) {

  if (array[j] < array[j - 1]) {

  int temp = array[j - 1];

  array[j - 1] = array[j];

  array[j] = temp;

  }

  //这个else是插入排序比较高效的关键,因为如果第i位置的前面的元素都排好序了,所以如果i位置比i-1位置小,就表示这趟排好序了

  else{

  break;

  }

  }

  }

  }

  复制代码

  可以看到,插入排序,是把当前i元素插入到之前合适的位置里,整个遍历的过程中,有break过程。

  它不像选择排序,为了找到最小的数,必须遍历完整个数组

  3.但是上面的程序稍显累赘,修改下

  复制代码

  public void sort(int[] array) {

  for (int i = 1; i < array.length; i++) {

  //把break条件放到for循环里面来,看起来很清爽

  for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {

  int temp = array[j - 1];

  array[j - 1] = array[j];

  array[j] = temp;

  }

  }

  }

  复制代码

  4.上面的程序仍然有问题,可以看到,每次交换都需要交换三个值,可以进一步修改一下

  复制代码

  public void sort(int[] array) {

  for (int i = 1; i < array.length; i++) {

  // 改进后的

  int e = array[i];

  int j;

  for (j = i; j > 0 && array[j - 1] > e; j--) {

  array[j] = array[j - 1];

  }

  array[j] = e;

  }

  }

  复制代码

  稍微解释一下:

  在内层循环中,把第i位置的数存下来,再依次遍历,如果第j-1位置的数比第j位置的数大,那么直接把j-1位置的数覆盖到第j位置

  直到找到i位置合适的位置为止,也就是array[j-1] < e 为止。

  最后才把刚刚存下来的数,赋值给找到的位置

  这样可以省去很多不必要的赋值过程,效率略显提高

  5.小结:

  对于插入排序,还想多说一句,插入排序虽然时间复杂度是O(n^2),但是在一定的场合,它的效率非常高。比如,在一个基本上有序的序列中,只有那么几个数,它的顺序不对,那么这时候,插入排序的效率非常高

  四、希尔排序

  1.希尔排序是插入排序一个强力改进版,思路是:

  先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

  因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

  2.实现:

  复制代码

  public void sort(int[] arr) {

  int n = arr.length;

  int h = 1;

  while (h < n / 3) {

  h = 3 * h + 1;

  }

  // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...

  while (h >= 1) {

  // h-sort the array

  for (int i = h; i < n; i++) {

  // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序

  int e = arr[i];

  int j;

  for (j = i; j >= h && e < arr[j - h]; j -= h) {

  arr[j] = arr[j - h];

  }

  arr[j] = e;

  }

  h /= 3;

  }

  }