最全的数据结构排序算法实现及比较

冒泡排序

类似暴力破解,1 – n 个,每个都比较一次。完成排序

public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len - 1; j++) {
            if (arr[i] > arr[j]) {
                SwapUtil.swap(arr, i, j);
            }
        }
    }
}

选择排序

[ 排序完毕 | 未排序] 每次从未排序的找一个最小的放入到排序完毕的后边

public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        int index = findMinIndex(arr, i);
        if (index !=  -1) {
            SwapUtil.swap(arr, i, index);
        }
    }
}
 
public int findMinIndex(int[] arr, int begin) {
    int len = arr.length;
    int index = -1, elem = arr[begin];
    for (; begin < len; begin++) {
        if (arr[begin] < elem) {
            index = begin;
            elem = arr[begin];
        }
    }
    return index;
}
堆排序

堆排序

先进行堆的构建,再进行堆的调整

@Override
public void sort(int[] arr) {
    int len = arr.length;
    sort(arr, len);
}
 
private void sort(int[] arr, int len) {
    buildMaxHeap(arr, len);
    adjust(arr, len);
}
 
private void adjust(int[] arr, int len) {
    for (int i = len - 1; i > 0; i--) {
        SwapUtil.swap(arr, 0, i);
        adjustHeap(arr, 0, i);
    }
}
 
private void buildMaxHeap(int[] arr, int len) {
    // 这里索引从 0 开始,所以最后一个非叶子子节点 array.length / 2 - 1;
    for (int i = len / BUILD_HEAP_SEPARATED - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }
    System.out.println("build heap : " + Arrays.toString(arr));
}
 
private void adjustHeap(int[] arr, int i, int length) {
    // 先把当前元素取出来,因为当前元素可能要一直移动
    int temp = arr[i];
    // 从左孩子开始遍历 ( 2i + 1)
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
        // 若右孩子存在,且右孩子大于左孩子
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            // 转移到右孩子
            k++;
        }
        // 如果发现结点(左右子结点)大于根结点,则进行值的交换
        if (arr[k] > temp) {
            SwapUtil.swap(arr, i, k);
            // 如果子节点更换了,则以子节点为根的子树会受到影响,
     // 所以,循环对子节点所在的树继续进行判断
            i  =  k;
        } else {
            //不用交换,直接终止循环
            break;
        }
    }
}

希尔排序

这里采用数组长度一半作为希尔增量进行排序,每次减少一半,知道增量为1.排序完毕。

 @Override
public void sort(int[] arr) {
    int step = arr.length / 2;
    for ( ; step > 0; step /= 2) {
        for (int i = step; i < arr.length; i++) {
            int value = arr[i];
            int j;
            // 跳跃的插入, 因为增量的存在,所以,后移时,是当前增量后移
            for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
                arr[j + step] = arr[j];
            }
            arr[j + step] = value;
        }
    }
 
}

插入排序

类似于选择排序,分为【排序 | 未排序区域】每次从未排序区域选取一个,再排序区域寻找位置,然后后移交换。

@Override
public void sort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int elem = arr[i];
        int index = getIndex(arr, i, elem);
        if (index != i) {
            retreat(arr, index, i);
            arr[index] = elem;
        }
    }
}
 
/**
 * 获取插入排序所在索引
 * @param arr 数组
 * @param limit 已排序区间上界
 * @param elem 待排序元素
 * @return 要插入的数组
 */
private int getIndex(int[] arr, int limit, int elem) {
    for (int i = 0; i < limit; i++) {
        if (elem < arr[i]) {
            return i;
        }
    }
    return limit;
}
 
/**
 * 将数组内一段元素后移
 * @param arr 数组
 * @param begin 区间下界
 * @param end 区间上界
 */
private void retreat(int[] arr, int begin, int end) {
    while(end > begin) {
        arr[end] = arr[end - 1];
        end--;
    }
}

二路归并排序

@Override
public void sort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}
 
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
 
public void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[arr.length];
    int leftIndex = left, rightIndex = mid + 1, tempIndex = left;
    while (leftIndex <= mid && rightIndex <= right) {
        if (arr[leftIndex] < arr[rightIndex]) {
            temp[tempIndex++] = arr[leftIndex++];
        } else {
            temp[tempIndex++] = arr[rightIndex++];
        }
    }
    while (leftIndex <= mid) {
        temp[tempIndex++] = arr[leftIndex++];
    }
    while(rightIndex <= right) {
        temp[tempIndex++] = arr[rightIndex++];
    }
    // 将归并结果归坏到原数组中
    while (left <= right) {
        arr[left] = temp[left++];
    }
}

快速排序

设数组第一个元素为基准,

第一步:数组中所有元素,小于 基准 放到左边,大于 基准 放到右边,此时数组分为两部分,对于基准来说已经处于它应处的位置

第二步,对左右两半数组继续执行第一步,递归完毕,数组有序

时间复杂度: O(n*log2n) – 空间复杂度: good: O(log2n) – bad: O(n)

@Override
public void sort(int[] arr) {
    int len = arr.length;
    sort(arr, 0, len - 1);
}
 
private void sort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = partition(arr, left, right);
        sort(arr, left, mid - 1);
        sort(arr, mid + 1, right);
    }
}
 
private int partition(int[] arr, int left, int right) {
    int sentry = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= sentry) {
            right--;
        }
        arr[left] = arr[right];
        while(left < right && arr[left] <= sentry) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = sentry;
    return left;
}

排序比较

排序方法 最好情况 最坏情况 平均情况 空间复杂度 稳定性
直接插入排序 O(n) O(n^2) O(n^2) O(1) 稳定
折半插入排序 O(nlong2n) O(n^2) O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(1) 不稳定
冒泡排序 O(n) O(n^2) O(n^2) O(1) 稳定
简单选择排序 O(n) O(n^2) O(n^2) O(1) 不稳定
快速排序 O(nlog2n) O(n^2) O(nlog2n) O(nlog2n) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(n+rd) 稳定

125jz网原创文章。发布者:江山如画,转载请注明出处:http://www.125jz.com/8811.html

(1)
江山如画的头像江山如画管理团队
上一篇 2020年10月12日 上午9:35
下一篇 2020年10月14日 上午9:13

99%的人还看了以下文章

  • python 初学者练手上机实操六-变量的定义及输入输出

    一、题目:打印诗“悯农” 要求: 1、新建一个“悯农.py” 2、编写程序。 3、调试程序。 4、排除错误。 二、题目:键盘输入三角形的三边,求三角形的周长。 1、新建一个triangle.py文件 2、编写程序。 3、调试程序。 4、排除错误。 三、定义三个变量分别存储你的姓名、班级、年龄并输出。 要求: 1、新建一个“info.py”文件 2、编写程序。…

    2023年6月15日
    6710
  • MySQL存储过程快速入门

    什么是存储过程 创建一个简单的存储过程 存储过程中的参数 存储过程的优势和不足 一、什么是存储过程 存储过程简单来说,就是为以后的使用而保存的一条或多条MySQL语句的集合。 一个存储过程是一个可编程的函数,它在数据库中创建并保存。它可以有SQL语句和一些特殊的控制结构组成。 存储过程就是一组SQL语句集,功能强大,可以实现一些比较复杂的逻辑功能 MySQL…

    2018年12月20日
    2.5K0
  • Python+ 人工智能软件工程师要学习哪些课程?

    1. Python 软件开发基础 2. Python 高级编程 3. Python 全栈式 WEB 工程师 4. Python 爬虫工程师、大数据分析工程师、人工智能工程师

    2018年12月27日
    3.4K0
  • python 初学者练手上机实操三

    一、题目:键盘输入三角形的三边,求三角形的周长。 1、新建一个triangle.py文件 2、编写程序。 3、调试程序。 4、排除错误。 二、题目:导入turtle包(import turtle),绘制边长为100的正方形。 要求: 1、新建一个“turtle2.py”文件 2、编写程序。 3、调试程序。 4、排除错误。 三、题目:打印诗“悯农” 要求: 1…

    2023年5月5日
    4980
  • JQuery change ()、.on(‘change’, function (){})事件只触发一次原因详解

    JQuery中使用  $(“input”).on(“change”,function(){})  仅仅会触发一次,第二次点击或输入不再触发。 JQuery change ()、.on(‘change’, function (){})事件只触发一次解决方法 (1)用jQuery的live代…

    2019年11月13日
    8.1K0
  • 推荐!学Python编程买什么样的电脑?(电脑配置清单)

    推荐购买台式机,性价比高于笔记本电脑。 当然对不差钱的可以买笔记本电脑,毕竟方便携带。 对于笔记本电脑: 推荐购买标准电压CPU的电脑(例如:第12代i7-12700H),H表示标准电压。 内存建议16G或以上 C盘建议固态硬盘256g以上 D盘建议1T以上(建议采用”内置“”固态硬盘+机械硬盘“的计算机,固态硬盘速度极快,用于运行系统和软件,机械硬盘空间大…

    2023年1月26日 编程开发
    5.9K0

发表回复

登录后才能评论