有序度:数组中具有有序关系的元素对的个数
有序元素对:a[i] <= a[j],如果i < j。
完全有序的数组,有序度就是 n * (n - 1) /2(满有序度)
逆序度 = 满有序度 - 有序度
冒泡排序
特性
- 原地
- 稳定
- O(n**2)(最少0次交换,最多n*(n-1)/2次交换)
冒泡排序每次比较相邻两数,若为逆序则交换,所以冒泡排序交换次数总是确定的,即为逆序度。
插入排序
特性
- 原地
- 稳定
- O(n**2)(将一个数据插入数组(O(n)),重复n次)
插入排序将数组分为两个区间:已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组首元素。每次取未排序区间元素在已排序区间中找到合适的位置插入,直到未排序区间为空。插入排序移动操作的次数是固定的,等于逆序度。
两种排序算法比较
虽然两种排序算法相同,都是原地、稳定排序,但插入排序要比冒泡排序更优
冒泡排序交换次数和插入排序数据移动次数一样,都等于逆序度
冒泡排序数据交换需要3个赋值操作,而插入排序数据移动只需要1个。
冒泡排序和插入排序Java实现
public class Sort {
/**
* 冒泡排序
*
* @param arr
* @param n
*/
public static void bubbleSort(int arr[], int n) {
if (n <= 1) return;
int count = 0;
//最多进行n - 1次冒泡
for (int i = 0; i < n; i++) {
boolean swaped = false;
for (int j = 0; j < n - i - 1; j++) {
//每次比较相邻数 把较大的放在后面
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
swaped = true;
}
}
count++;
if (!swaped) break;
}
System.out.println("进行了" + count + "次冒泡");
}
/**
* 插入排序
*
* @param arr
* @param n
*/
public static void inserctionSort(int arr[], int n) {
if (n <= 1) return;
//将数组分为已排序部分和未排序部分
for(int i = 1; i < n; i++) {
int value = arr[i];//未排序部分的第一个值
int j = i - 1;
//每次将未排序部分的第一个值插入已排序部分中
for(; j >= 0; j--){
//寻找插入点 arr[j]为第一个小于等于value的值
if(arr[j] > value)
arr[j + 1] = arr[j];
else
break;
}
//将value插入到j后面
arr[j + 1] = value;
}
}
public static void sortTest() {
int arr[] = {3, 5, 4, 1, 2, 6};
printArr(arr);
inserctionSort(arr, arr.length);
printArr(arr);
}
public static void printArr(int arr[]) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}