java实现折半排序算法

Java实现折半排序算法

折半排序（Binary Insertion Sort）是插入排序的一种改进版本，与插入排序相同的是，该算法的平均时间复杂度也为O(n^2)，但是折半排序的优势在于其最坏时间复杂度为O(n^2)。

1. 算法原理

折半排序的算法原理如下：

1. 从第2个元素开始，依次将元素插入到已排序的序列中。
2. 每次插入时使用折半查找的方式，找到插入元素应该的位置，然后将该位置及其后面的所有元素全部后移一位。
3. 在空出来的位置插入该元素。

2. 代码实现

以下是Java实现折半搜索排序算法的完整代码：

public static void binaryInsertionSort(int[] arr) {  
    int len = arr.length;  
    int left, right,  mid, temp;  
    for (int i = 1; i < len; i++) {
        temp = arr[i]; 
        left = 0;  
        right = i - 1;  
        while (left <= right) {  
            mid = (left + right) / 2;  
            if (arr[mid] > temp) {  
                right = mid - 1;  
            } else {  
                left = mid + 1;  
            }  
        }  
        for (int j = i - 1; j >= left; j--) {  
            arr[j + 1] = arr[j];  
        }  
        arr[left] = temp;  
    }  
} 

3.示例说明

下面以一个数组{8,2,4,9,3,6}为例来演示该算法的运行过程。

首先进行第一次插入：

temp = 2;
left = 0;
right = 0;

while (left <= right) {
    mid = (left + right) / 2;
    if (arr[mid] > temp) {
        right = mid -1;
    } else {
        left = mid + 1;
    }
}

for (int j = 0; j >= left; j--) {  
    arr[j + 1] = arr[j];  
}  
arr[left] = temp;  

在第一次插入中，将2插入到序列中，并得到排好序的序列{2,8}。

接下来，进行第二次插入：

temp = 4;
left = 0;
right = 1;

while (left <= right) {
    mid = (left + right) / 2;
    if (arr[mid] > temp) {
        right = mid -1;
    } else {
        left = mid + 1;
    }
}

for (int j = 1; j >= left; j--) {  
    arr[j + 1] = arr[j];  
}  
arr[left] = temp;  

在第二次插入中，将4插入到序列中，并得到排好序的序列{2,4,8}。

依次进行下去，可以得到最终的排好序的序列：

{2,3,4,6,8,9}

4.总结

折半排序是一种简单且易于实现的排序算法，虽然其平均时间复杂度与插入排序相同，但是在某些情况下其最坏时间复杂度可以更优，因此也具有一定的实际应用价值。用户在应用该算法时，应根据具体情况选择适当的排序算法，以取得更好的排序效果。