由于需要分析算法的最好时间复杂度和最坏时间复杂度,因此这篇文章中写的排序都是从小到大的升序排序。

带排序的数组为arr,arr的长度为N。时间复杂度使用TC表示,额外空间复杂度使用SC表示。

好多代码都用到了交换arr[i]和arr[j]的地方,这里先给出代码。

private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

 

(1)插入排序

1.1直接插入排序

算法思想:初始时第一个元素是有序的,在插入元素arr[i]时,arr[0] ~arr[i – 1]已经是有序的了,将arr[i]插入其中即可。

稳定性:如果遇到和arr[i]相等的元素,那么将arr[i]放在后面,所以直接插入排序是稳定的。

复杂度分析:arr基本有序(升序)时,直接插入排序的TC是O(N);arr降序时,TC是O(N*N);平均时间复杂度O(N*N)。直接插入排序的SC是O(1)。

算法实现:

public class InsertionSort_StraightInsertionSort {
    public static int[] sis(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
        return arr;
    }
}

1.2希尔排序

算法思想:希尔排序的实质就是分组插入排序,该方法又称为缩小增量排序。先将arr分割成若干个子序列(由相隔某个增量的元素组成),分别进行直接插入排序,然后依次缩小增量再进行排序。待整个序列中的元素基本有序(增量足够小时),再对全体元素进行一次直接插入排序。

稳定性:不稳定

复杂度分析:TC最好为O(N) ,最坏 O(N * N),平均TC为O(N*1.3)。SC为O(1)。

算法实现:

public class InsertionSort_ShellSort {
 public static int[] shellSort(int[] arr) {
     for (int gap = arr.length / 2; gap > 0; gap /= 2) {
         for (int i = gap; i < arr.length; i++) {
             for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
                 swap(arr, j, j + gap);
             }
         }
     }
     return arr;
 }
}

(2)交换排序

2.1冒泡排序

算法思想:一次比较两个元素,如果他们的顺序错误就把他们交换过来。

稳定性:稳定

复杂度分析:arr升序时TC最好为O(N) ,arr降序时TC最坏 O(N * N),平均TC为O(N*N)。SC为O(1)

算法实现:

public class Exchange_Bubble {
    public static int[] bubbleSort(int[] arr) {
        for (int i = arr.length; i != 0; i--) {
            for (int j = 1; j < i; j++) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j - 1, j);
                }
            }
        }
        return arr;
    }
}

2.2快速排序

算法思想:1.先从数列中取出一个数作为基准数;2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。3.再对左右区间重复第二步,直到各区间只有一个数。

稳定性:不稳定

复杂度分析:arr升序时TC最好为O(NLogN) ,arr降序时TC最坏 O(NLogN),平均TC为O(NLogN)。SC为O(1)

算法实现:

public class Exchange_QuickSort {

    public static int[] quickSort1(int[] arr) {
        return qs1(arr, 0, arr.length - 1);
    }

    private static int[] qs1(int[] arr, int left, int right) {
        if (left > right) {
            return arr;
        }
        int i = left;
        int j = right;
        int tmp = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= tmp) {
                j--;
            }
            while (i < j && arr[i] <= tmp) {
                i++;
            }
            if (i < j) {
                swap(arr, i, j);
            }
        }
        arr[left] = arr[i];
        arr[i] = tmp;

        qs1(arr, left, i - 1);
        qs1(arr, i + 1, right);
        return arr;
    }
}

(3)选择排序

3.1简单选择排序

算法思想:在要排序的一组数中,选择出最小的数与第一个数交换;然后在剩下的数中,选择出最小的数与第二个数交换,以此类推。

稳定性:稳定

复杂度分析:arr升序时,只是避免了交换元素的操作,TC最好仍旧为O(N*N) ;arr降序时TC最坏 O(N*N),平均TC为O(N*N)。SC为O(1)

算法实现:

public class SelectionSort_SimpleSelectionSort {
    public static int[] simpleSelectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            if (arr[minIdx] < arr[i]) {
                swap(arr, minIdx, i);
            }
        }
        return arr;
    }
}

3.2堆排序

算法思想:从小到大排序,构建大顶堆(堆首先是一棵完全二叉树,大顶堆每个节点的值都不大于父节点的值),然后每次将堆顶元素和没有排序的最后的元素交换,重新构建堆(即重新得到最大的堆顶元素)。

稳定性:不稳定

复杂度分析:

最好情况:如果待排序数组是降序的,仍然需要O(N * logN)复杂度的比较操作,少了移动的操作;

最坏情况:如果待排序数组是升序的,不仅需要O(N * logN)复杂度的比较操作,而且需要O(N * logN)复杂度的交换操作。总的时间复杂度还是O(N * logN)。

在最好和最坏情况下,堆排序的时间复杂度都是O(NlogN)。堆排序时,由于每次重新恢复堆的时间复杂度为O(logN),共N – 1次堆调整操作,再加上前面建立堆时N / 2次向下调整,

每次调整时间复杂度也为O(logN)。两次次操作时间相加还是O(N * logN)。故堆排序的时间复杂度为O(N * logN)。

堆排序一般优于快速排序的重要一点是,数据的初始分布情况对堆排序的效率没有大的影响

算法实现:

public class SelectionSort_HeapSort {
    public static int[] heapSort(int[] arr) {
        buildHeap(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);//交换完后,大的元素跑到了数组的后面的部分  所以堆排序时 数组后面到前面逐渐变得有序
            heapify(arr, 0, i); //调整回大顶堆,即重新找到未排序部分的最大值
        }
        return arr;
    }
    private static void buildHeap(int[] arr) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }
    }
    //从index开始往下不断调整大顶堆
    private static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;
        while (left < heapSize) {
            if (arr[left] > arr[index]) {
                largest = left;
            }
            if (right < heapSize && arr[right] > arr[largest]) {
                largest = right;
            }
            if (largest != index) {
                swap(arr, largest, index);
            } else {
                break;
            }
            index = largest;
            left = index * 2 + 1;
            right = index * 2 + 2;
        }
    }
}

(4)不基于比较的排序

4.1桶排序

算法思想:桶排序可用于最大最小值相差较大的数据情况,要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中。

把数组 arr 划分为n个大小相同子区间(桶),每个子区间各自排序,最后合并。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值max、最小值min;2.我们使用 动态数组ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr,计算每个元素 arr[i] 放的桶;4.每个桶各自排序;5.遍历桶数组,把排序好的元素放进输出数组

稳定性:稳定

复杂度分析:

N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+N*logN-N*logM) 
当N=M时,即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。
桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

算法实现:

public class NoCompare_BucketSort {
    public static int[] bucketSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int cur : arr) {
            max = Math.max(max, cur);
            min = Math.min(min, cur);
        }
        //计算桶的数量并构建初始的桶
        int bucketNum = (max - min) / arr.length + 1;
//        int bucketNum = (max - min) + 1;      //每个桶中只有一个元素的时候就是计数排序
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }
        //将每个元素放到桶中
        for (int cur : arr) {
            int index = (cur - min) / arr.length;
//            int index = (cur - min);  //每个桶中只有一个元素的时候就是计数排序
            buckets.get(index).add(cur);
        }
        //对每个桶内的元素进行排序,可以使用直接插入排序等排序方法
        int index = 0;
        for (List<Integer> bucket : buckets) {
            insertSort(bucket);
            for (int cur : bucket) {
                arr[index++] = cur;
            }
        }
        return arr;
    }
    
    private static void insertSort(List<Integer> bucket) {
        Integer[] arr = bucket.toArray(new Integer[bucket.size()]);
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            bucket.set(i, arr[i]);
        }
    }
}

4.2基数排序

算法思想: 基数排序(Radix Sort)是一种非比较型排序算法,它将整数按位数切割成不同的数字,然后按每个位分别进行排序。

基数排序的方式可以采用MSD(Most significant digital)或LSD(Least significant digital),MSD是从最高有效位开始排序,而LSD是从最低有效位开始排序。当然我们可以采用MSD方式排序,按最高有效位进行排序,将最高有效位相同的放到一堆,然后再按下一个有效位对每个堆中的数递归地排序,最后再将结果合并起来。但是,这样会产生很多中间堆(高位排序比低位排序多了空间开销)。所以,通常基数排序采用的是LSD方式。LSD基数排序实现的基本思路是将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

需要注意的是,对每一个数位进行排序的算法必须是稳定的,否则就会取消前一次排序的结果。

稳定性:稳定

复杂度分析:设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。

空间效率:需要2*radix个指向队列的辅助空间,以及用于静态链表的n个指针。

算法实现:

public class NoCompare_RadixSort {
    public static int[] radixSort(int[] arr) {
        int maxLen = getMaxBit(arr);//得到arr中最大的数的长度
        int[] tmp = new int[arr.length];
        int[] count = new int[10];// 计数器
        int radix = 1;
        for (int i = 1; i <= maxLen; i++) {// 进行maxLen次排序
            Arrays.fill(count, 0);// 每次分配前清空计数器

            for (int j = 0; j < arr.length; j++) {
                int k = (arr[j] / radix) % 10;// 统计每个桶中的记录数
                count[k]++;
            }
            for (int j = 1; j < 10; j++) {
                count[j] = count[j - 1] + count[j];// 将tmp中的位置依次分配给每个桶
            }
            for (int j = arr.length - 1; j != -1; j--) {// 将所有桶中的记录依次收集到tmp中
                int k = (arr[j] / radix) % 10;
                tmp[count[k] - 1] = arr[j];
                count[k]--;
            }
            for (int j = 0; j < arr.length; j++) {// 将临时数组的内容复制到arr中
                arr[j] = tmp[j];
            }
            radix = radix * 10;
        }
        return arr;
    }

    // 得到arr中最大的数的长度
    private static int getMaxBit(int[] arr) {
        int maxNum = Integer.MIN_VALUE;
        for (int cur : arr) {
            maxNum = Math.max(maxNum, cur);
        }
        return String.valueOf(maxNum).length();
    }
}

(5)归并排序

算法思想:

将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行合并。
可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,
可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

 

稳定性:稳定

复杂度分析:最好、最坏、平均TC都是O(NlogN)。SC是O(N)

算法实现:

 

public class MergeSort {
    //将arr[first~mid]和arr[mid~last]合并到tmp中
    private static void mergeArray(int[] arr, int first, int mid, 
            int last, int[] tmp) {
        int begin1 = first;
        int begin2 = mid + 1;
        int end1 = mid;
        int end2 = last;
        int k = 0;
        while (begin1 <= end1 && begin2 <= end2) {
            if (arr[begin1] < arr[begin2]) {
                tmp[k++] = arr[begin1++];
            } else {
                tmp[k++] = arr[begin2++];
            }
        }
        while (begin1 <= end1) {
            tmp[k++] = arr[begin1++];
        }
        while (begin2 <= end2) {
            tmp[k++] = arr[begin2++];
        }
        //将辅助数组tmp的数据写回arr
        for (begin1 = 0; begin1 < k; begin1++) {
            arr[first + begin1] = tmp[begin1];
        }
    }
    public static int[] mergeSort(int[] arr, int first, 
            int last, int[] tmp) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergeSort(arr, first, mid, tmp);//左边有序
            mergeSort(arr, mid + 1, last, tmp);//右边有序
            mergeArray(arr, first, mid, last, tmp);//将两个有序数列合并
        }
        return arr;
    }
}

 

此外,为了验证结果的正确性,可以写个和Arrays.sort()方法比较的代码。getIntArr得到一个大小是size,最大值小于bound的int数组。arrEquals比较两个int数组是否相等。

public class MyUtil {
    public static int[] getIntArr(int size, int bound) {
        int[] arr = new int[size];
        Random r = new Random();
        for (int i = 0; i < size; i++) {
            arr[i] = r.nextInt(bound);
        }
        return arr;
    }
    
    public static boolean arrEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

以直接插入排序为例,我们可以这么用MyUtil。

public static void main(String[] args) {
        int times = 0;
        while (times++ < 100) {
            int[] arr = MyUtil.getIntArr(50, 100);
            int[] brr = arr.clone();
            Arrays.sort(arr);
            if (!MyUtil.arrEquals(arr, sis(brr))) {
                System.out.println("Something Wrong");
            }
        }
        System.out.println("Everything is OK.");
}

 

版权声明:本文为sodawoods-blogs原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/sodawoods-blogs/p/8681260.html