冒泡排序、选择排序与插入排序的比较

冒泡排序、选择排序与插入排序的比较

选择排序(O(n^2))

基本思想：每一趟从待排序的数据元素中选择最小或者最大的一个元素作为首元素，直到所有元素排完为止，它是一种不稳定的排序。

/*** 简单选择排序** @param arr*/public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) {min = j;}}//进行交换，如果min发生变化，则进行交换if (min != i) {swap(arr,min,i);}}}

冒泡排序(O(n^2))

基本思想：对相邻的元素进行两两比较，顺序相反的则进行交换，这样，每一趟会将最小或最大的元素“浮到”顶端，最终达到完全要有序

/*** 冒泡排序** @param arr*/public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {swap(arr,j,j+1);flag = false;}}if (flag) {break;}}}

插入排序(O(n^2))

基本思想：每一步将一个待排序的记录，插入到前面已经排好序的有序序列中，直到插完所有元素为止。

/*** 插入排序** @param arr*/public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int j = i;while (j > 0 && arr[j] < arr[j - 1]) {swap(arr,j,j-1);j--;}}}

虽然这三种排序的时间复杂度都是(O(n^2))，但是根据最好最差情况的判断，插入排序优于选择排序，选择排序优于冒泡排序。