亲宝软件园·资讯

展开

Java 排序 Java重点之基于比较的七大排序

小玄ks 人气:0
想了解Java重点之基于比较的七大排序的相关内容吗,小玄ks在本文为您仔细讲解Java 排序的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,排序,Java,比较排序,下面大家一起来学习吧。

七大基于比较的排序

直接插入排序

思想:以双指针来进行遍历数组和寻找较小元素的操作,每次找到较小元素的时候就将其插入到前面的适当位置,当遍历完整个数组,并完成插入操作后,排序完成。

时间复杂度:最好情况:O(N)
最坏情况:O(N^2)
空间复杂度:O(1)
结论:当一组数据趋近于有序,适用于插入排序

public static void insertSort(int[] array) {
        //该循环实现对整个数组的遍历操作
        for (int i = 1; i < array.length; ++i) {
            
            //记录将被插入的元素(i下标元素)
            int tmp = array[i];
            //j指向i的前一个元素
            int j = i - 1;

            for (; j >= 0; j--) {
                //如果j指向的元素比被插入元素大,就往后移一位
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {//否则就找到了插入位置,跳出该循环
                    break;
                }
            }

            
            //j+1即为插入位置
            array[j + 1] = tmp;
        }
}

希尔排序

思想:将数组不断分组再进行排序,当分组的长度为1时,进行的就是直接插入排序。

时间复杂度:O(N1.3 ~ N1.5)
空间复杂度:O(1)

public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            //gap为1时,就是直接插入排序
            gap = gap / 3 + 1;
            shell(array, gap);
        }
}
public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; ++i) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
}

选择排序

思想:选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置直到未排序元素个数为0。

时间复杂度:O(N2)

空间复杂度:O(N2)

public static void selectSort(int[] array){
    for(int i = 0;i<array.length;++i){
        for(int j = i+1;j<array.length;++j){
            if(array[j]<array[i]){
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }
    }
}

堆排序

思想:从小到大排序,就先建一个大堆,堆头元素就是整个数组中最大的数,==因此我们每次将堆头元素与堆尾元素交换,交换一次,堆尾下标往前移动一位,形成一个新堆,再向下调整构建成大堆;==以此循环,直到堆尾下标与堆头下标重合,堆排序完成。

时间复杂度:O(N*log N)

空间复杂度:O(1)

public static void heapSort(int[] array) {
        createHeap(array);//建大堆
        int end = array.length - 1;
    //将堆头元素与堆尾元素互换位置,就将最大元素放到了最后一位,舍去最后一位小标重新将堆向下调整;直到堆为空,数组中元素就排序完成。
        while (end >= 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            end--;
            siftDown(array, 0, end);
        }
    }
	//从小到大排序,建一个大堆
	public static void createHeap(int[] array) {
        for (int parent = (array.length - 1) / 2; parent >= 0; parent--) {
            siftDown(array, parent, array.length-1);
        }
    }

	//向下调整大堆
    public static void siftDown(int[] array, int root, int end) {
        int parent = root;
        int child = 2 * parent + 1;
        while (child <= end) {
            if (child + 1 <= end && array[child] < array[child + 1])
                child++;
            if (array[parent] < array[child]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

冒泡排序

思想:相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。该冒泡排序为优化过的排序,定义一个boolean类型的变量来判断数组是否已经有序,若有序可以直接返回,以此来减少时间复杂度。

时间复杂度:最坏:O(N2)

​ 最优:O(N)

空间复杂度:O(1)

 public static void bubbleSort(int[] array) {
     //最外层循环为比较的趟数
        for (int i = 0; i < array.length - 1; ++i) {
            //flag是为了判断接下来的循环是否有必要进行
            boolean flag = false;
            //内层循环为每趟比较的次数
            for (int j = 0; j < array.length - 1 - i; ++j) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            //flag==false说明这趟循环没有交换数据,也就是说数组已经有序,可以直接返回。
            if (flag == false) return;

        }
    }

快速排序

思想:先找到一个中间元素,将小于这个元素的数放到它的左边,大于这个元素的数放到它的右边,再将左右两部分进行上述操作,重复以往,就完成快排操作。
时间复杂度:最好:O(Nlog 2N)
最坏:O(N2)
时间复杂度平均:O(Nlog2N)
空间复杂度:O(Nlog2N)

public static void quickSort(int[] array, int l, int r) {
        if (l >= r) return;
    //因为用do while()循环,所以先将左右指针向两边移动一位
        int i = l - 1, j = r + 1;
    //取数组中间元素的值作为这个分割点
        int mid = array[(l + r)>>1];

        while (i < j) {
            //左边的数小于中间值,指针向右移动
            do ++i; while (array[i] < mid);
            //右边的数大于中间值,指针向左移动
            do --j; while (array[j] > mid);
            //两个指针停下后交换元素
            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }

        }
    //递归左半部分
        quickSort(array, l, j);
    //递归右半部分
        quickSort(array, j + 1, r);


    }

归并排序

思想:先分组再排序,和快排操作顺序相反。将数组分为左右两部分,再对左右两部分 分别再分组,以此类推,直到每一部分只有一个元素,然后按顺序合并为一个个新的有序数组,小数组归并为大数组,以此类推就得到排序后的数组。

时间复杂度:O(N*logN)

空间复杂度:O(N)

 public static void mergeSort(int[] array){
        mergerSortInternal(array,0,array.length-1);
    }
    public static void mergerSortInternal (int[] array,int l,int r){
        if(l>=r)    return;
        int mid = (l+r)>>1;
        //递归左半部分
        mergerSortInternal(array,l,mid);
        //递归右半部分
        mergerSortInternal(array,mid+1,r);
        //归并
        merge(array,l,mid,r);
    }
    public static void merge(int[] array,int l,int mid, int r){
        int s1 = l,e1 = mid;
        int s2 = mid+1, e2 = r;
        int [] tmp = new int[r-l+1];
        int k = 0;
        //比较两个有序小数组元素,将小的元素放到新数组前面,大的元素放到新数组后面
        while(s1<=e1 && s2<=e2){
            if(array[s1]<array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k++] = array[s2++];
            }
        }
        //处理剩余元素
        while(s1<=e1)   tmp[k++] = array[s1++];
        while(s2<=e2)   tmp[k++] = array[s2++];
        //将排完序的新数组元素放回原数组中
        for(int i = 0;i<tmp.length;++i){
            array[i+l] = tmp[i];
        }
    }

加载全部内容

相关教程
猜你喜欢
用户评论