冒泡排序
冒泡算法的运作规律如下:
①、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
②、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成)。
③、针对所有的元素重复以上的步骤,除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
|
public class BubbleSort { public static int[] sort(int[] array) { for (int i = 1; i < array.length; i++) { boolean flag = true; for (int j = 0; j < array.length - i; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; flag = false; } } if (flag) { break; } System.out.print("第"+i+"轮排序后的结果为:"); display(array);
} return array; }
public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); }
public static void main(String[] args) { int[] array = {4,2,8,9,5,7,6,1,3}; System.out.println("未排序数组顺序为:"); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("经过冒泡排序后的数组顺序为:"); display(array); }
}
|
选择排序
选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
分为三步:
①、从待排序序列中,找到关键字最小的元素
②、如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换
③、从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
|
public class ChoiceSort { public static int[] sort(int[] array){ for(int i = 0 ; i < array.length-1 ; i++){ int min = i; for(int j = i+1 ; j < array.length ; j++){ if(array[j]<array[min]){ min = j; } } if(i != min){ int temp = array[i]; array[i] = array[min]; array[min] = temp; } System.out.print("第"+(i+1)+"轮排序后的结果为:"); display(array); } return array; }
public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); }
public static void main(String[] args){ int[] array = {4,2,8,9,5,7,6,1,3}; System.out.println("未排序数组顺序为:"); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("经过选择排序后的数组顺序为:"); display(array); }
}
|
插入排序
直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。
插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
public class InsertSort { public static int[] sort(int[] array){ int j; for(int i = 1 ; i < array.length ; i++){ int tmp = array[i]; j = i; while(j > 0 && tmp < array[j-1]){ array[j] = array[j-1]; j--; } array[j] = tmp; } return array; }
public static void display(int[] array){ for(int i = 0 ; i < array.length ; i++){ System.out.print(array[i]+" "); } System.out.println(); }
public static void main(String[] args){ int[] array = {4,2,8,9,5,7,6,1,3}; System.out.println("未排序数组顺序为:"); display(array); System.out.println("-----------------------"); array = sort(array); System.out.println("-----------------------"); System.out.println("经过插入排序后的数组顺序为:"); display(array); }
}
|
总结
上面讲的三种排序,冒泡、选择、插入用大 O 表示法都需要 O(N2) 时间级别。一般不会选择冒泡排序,虽然冒泡排序书写是最简单的,但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低,但是比较次数还是挺大的。当数据量小,并且交换数据相对于比较数据更加耗时的情况下,可以应用选择排序。
在大多数情况下,假设数据量比较小或基本有序时,插入排序是三种算法中最好的选择。