6种常见排序算法(java版)

2023-10-31 08:23:51

1、排序算法基本概念

1.1、什么是排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。（摘自百科）

1.2、排序算法稳定性说明

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
假定我们拥有一个数据库表，里面记录了学生的出生年份和出生月份，分别记为year和month，我们先按月份将该表中的数据排好序。如下：

year(年份)month(月份)
19921
19911
19923
19934
19928
199212
此时如果继续按照年份排序，如果选择一个不稳定的排序，可能会导致1992年的原本排序打乱，出现如下结果：
year(年份)month(月份)
19911
19923
19921
199212
19928
19934

显然不稳定的排序会导致原本的排序被打乱，出现我们不想要的结果。

1.3、排序算法的分类

从是否全部使用内存的角度可以分为：

  • 内部排序：只使用内存，常见的算法有插入排序、选择排序、冒泡排序、堆排序、快速排序。
  • 外部排序：借助磁盘等辅存，常用于大量数据排序，一次性不能装入内存。常见算法有归并排序、计数排序、基数排序、桶排序。

从使用方法上可以分为：

  • 插入：每次插入元素至已有序列，常见有直接插入排序、希尔排序等
  • 选择：每次选择最大或最小元素，常见有直接选择排序、堆排序等
  • 交换：每次使用交换两个元素的方式，常见有冒泡排序、快速排序等
  • 归并：分组后合，常见有并归并排序等
  • 其他：基数排序、桶排序等

2、常见排序算法

2.1、插入排序

每次将一个元素插入至一个排好序的序列中。针对一个未排序的数列，我们首先选择首元素，然后遍历，依次插入第2个、第3个…，每次插入元素时从已排好序的元素右边开始比较，如果小于该元素，交换。直至大于被比较元素。

算法时间复杂度
最好：O(n)
平均：O(n^2)
算法空间复杂度：O(1)
稳定性：稳定

算法实现：

/**
* @param datas 待排序序列
*/@Overridepublicvoidsort(int[] datas) {for (int i =1; i < datas.length; i++) {int j = i -1;int sel_num = datas[i];while (j >=0 && sel_num < datas[j]) {
            datas[j +1] = datas[j--];
        }
        datas[j +1] = sel_num;
    }
}

2.1、选择排序

每次从待排序序列中选择最小的一个元素。针对一个未排序数列，首先从中选择最小的一个数，然后再从剩下的元素中选择次小的数，直到待排序数列为空。
算法实现：

算法时间复杂度
最好：O(n^2)
平均：O(n^2)
算法空间复杂度：O(1)
稳定性：不稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {for (int i =0; i < datas.length; i++) {int minIndex = i;for (int j = i +1; j < datas.length; j++) {if (datas[minIndex] > datas[j]) {
                minIndex = j;
            }
        }int temp = datas[minIndex];
        datas[minIndex] = datas[i];
        datas[i] = temp;
    }
}

2.3、冒泡排序

针对未排序数列，自下而上的一次比较相邻的两个数，让较小的数排上上面，这样一趟下来，最小的数就会排在第一个，然后重复该操作。
代码实现：

算法时间复杂度
最好：O(n^2)，可改进成O(n),算法判断扫描时是否交换过位置
平均：O(n^2)
算法空间复杂度：O(1)
稳定性：稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {for (int i =0; i < datas.length-1; i++) {for (int j = datas.length -1; j > i; j--) {if(datas[j]<datas[j-1]){int temp = datas[j];
                datas[j] = datas[j-1];
                datas[j-1] = temp;
            }
        }
    }
}

2.4、快速排序

选择一个基准元素，然后用这个元素将待排序数组分成两部分，一部分在左边，都比基准元素小，一部分在右边都比基准元素大。针对左右两边的数列重复该方法。

算法时间复杂度
最好：O(n*log2n)
最坏：O(n^2) 待排序数列已是排好序的
平均：O(n*log2n)
算法空间复杂度：O(n*log2n)
稳定性：不稳定

算法实现1：

/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @paramend 待排序序列结束位置
*/public void sort(int[] datas) {
    sort(datas,0, datas.length -1);
}private void sort(int[] datas,int start,intend) {if (start <end) {int selNum = datas[start];intleft = start;intright =end;while (right !=left) {while (left <right && selNum < datas[right]) {right--;
            }while (left <right && selNum >= datas[left]) {left++;
            }int temp = datas[left];
            datas[left] = datas[right];
            datas[right] = temp;
        }
        datas[left] = selNum;
        sort(datas, start,left -1);
        sort(datas,left +1,end);
    }
}

算法实现2：

/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
    sort(datas,0, datas.length -1);
}/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @param end 待排序序列结束位置
*/privatevoidsort(int[] datas,int start,int end) {if(start >= end){return;
    }int index = start;int selNum = datas[end];int temp;for (int i = start; i < end ; i++) {if (selNum > datas[i]) {
            temp = datas[index];
            datas[index] = datas[i];
            datas[i] = temp;
            index++;
        }
    }
    temp = datas[index];
    datas[index] = datas[end];
    datas[end] = temp;
    sort(datas,start,index-1);
    sort(datas,index+1,end);
}

2.5、堆排序

使用完全二叉树保存待排序数列，将该二叉树变成大根堆，然后交换对顶元素和最后一个元素，然后调整使该二叉树回归至大根堆。重复执行直至堆大小为1。
算法实现：

算法时间复杂度
最好：O(n*log2n)
最坏：O(n*log2n) 
平均：O(n*log2n)
算法空间复杂度：O(1)
稳定性：不稳定
/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
    buildMaxHeap(datas);int len = datas.length;for (int i = len -1; i >0; i--) {
        swap(datas,0, i);
        maxHeapify(datas,0, i);
    }
}/**
* 构建最大堆
* @param datas 待排序序列
*/privatevoidbuildMaxHeap(int[] datas) {int endIndex = parent(datas.length);for (int i = endIndex; i >=0; i--) {
        maxHeapify(datas, i, datas.length);
    }
}/**
* 调整最大堆，使恢复至最大堆
* @param datas 待排序序列
* @param index 待调整元素位置
* @param heapSize 堆大小
*/privatevoidmaxHeapify(int[] datas,int index,int heapSize) {int indexMax = index;int left = leftChild(index);if ((left +1) <= heapSize && datas[indexMax] < datas[left]) {
        indexMax = left;
    }int right = rightChild(index);if ((right +1) <= heapSize && datas[indexMax] < datas[right]) {
        indexMax = right;
    }if (index != indexMax) {
        swap(datas, index, indexMax);
        maxHeapify(datas, indexMax, heapSize);
    }
}privatevoidswap(int[] datas,int i,int j) {int temp = datas[i];
        datas[i] = datas[j];
        datas[j] = temp;
}/**
* 求元素父元素位置
* @param index 元素位置（从0开始）
*/privateintparent(int index) {return (index +1) /2 -1;
}/**
* 求元素左孩子元素位置
* @param index 元素位置（从0开始）
*/privateintleftChild(int index) {return (index +1) *2 -1;
}/**
* 求元素有孩子元素位置
* @param index 元素位置（从0开始）
*/privateintrightChild(int index) {return (index +1) *2;
}

2.6、归并排序

首先将待排序数列分成两部分，然后遍历将每部分再分为两部分，直至每一部分只包含一个元素，然后在依次将每一部分合并成一个有序数列。

算法时间复杂度
最好：O(n*log2n)
最坏：O(n*log2n) 
平均：O(n*log2n)
算法空间复杂度：O(1)
稳定性：稳定

算法实现：

/**
* @param datas 待排序序列
*/publicvoidsort(int[] datas) {
    sort(datas,0, datas.length -1);
}/**
* @param datas 待排序序列
* @param start 待排序序列起始位置
* @param end 待排序序列结束位置
*/privatevoidsort(int[] datas,int start,int end) {if (end == start) {return;
    }int splitLen = start + (end - start) /2;
    sort(datas, start, splitLen);
    sort(datas, splitLen +1, end);
    merge(datas, start, splitLen, end);
}/**
* @param datas 待排序序列
* @param start 待合并序列起始位置
* @param splitLen 待合并序列中间分隔位置
* @param end 待合并序列结束位置
*/privatevoidmerge(int[] datas,int start,int splitLen,int end) {int i =0, j =0;int[] temp =newint[end - start +1];while (i <= splitLen - start && j <= end - splitLen -1) {if (datas[start + i] <= datas[splitLen +1 + j]) {
            temp[i + j] = datas[start + i];
            i++;
        }else {
            temp[i + j] = datas[splitLen +1 + j];
            j++;
        }
    }for (int k = i; k <= splitLen - start; k++) {
        temp[k + j] = datas[start + k];
    }for (int k = j; k <= end - splitLen -1; k++) {
        temp[k + i] = datas[splitLen +1 + k];
    }for (int k = start; k <= end; k++) {
        datas[k] = temp[k-start];
    }
}


  • 作者：linpeng123l
  • 原文链接：https://blog.csdn.net/linpeng123l/article/details/52317351
    更新时间：2023-10-31 08:23:51