8大Java排序方法(由简入繁)，有代码详解和原理指导
Java8大排序方法
·
1. 插入排序
升序：
public static void main(String [] args) {
int j;
int[] array = {14,98,36,80,28,99,55,32};
for(int i = 1 ; i < array.length ; i++) {
int temp1 = array[i];
for(j = i-1 ; j >= 0 && array[j] < temp1 ; j--) {
array[j+1] = array[j];
}
array[j+1] = temp1;
}
}
降序：
public static void main(String [] args) {
int j;
int[] array = {14,98,36,80,28,99,55,32};
for(int i = 1 ; i < array.length ; i++) {
int temp1 = array[i];
for(j = i-1 ; j >= 0 && array[j] > temp1 ; j--) {
array[j+1] = array[j];
}
array[j+1] = temp1;
}
}
原理：
- 初始化：从数组的第二个元素开始迭代，因为单个元素默认是已排序的。
- 选择未排序的元素：
array[i]是需要被插入到已排序子数组中的元素。 - 寻找插入位置：内部循环用于对已排序的部分进行扫描，检查当前
array[j]是否小于temp1。如果是，这意味着temp1应该被插入到array[j]的后面。 - 插入元素：当内部循环结束时，我们找到了
temp1的正确位置，这个位置是j + 1。
2. 选择排序
升序：
public static void main(String[] args) throws ParseException {
int[] array = {14, 98, 36, 80, 28, 99, 55, 32};
for (int i = 0; i < array.length - 1; i++) {
final int MAX_POS = array.length - 1 - i;
int MAX_VAL_POS = 0;
for (int j = 1; j <= MAX_POS; j++) {
if (array[j] > array[MAX_VAL_POS]) {
MAX_VAL_POS = j;
}
}
if (MAX_VAL_POS != MAX_POS) {
int temp = array[MAX_VAL_POS];
array[MAX_VAL_POS] = array[MAX_POS];
array[MAX_POS] = temp;
}
}
}
降序：
public static void main(String [] args) {
int[] array = {14, 98, 36, 80, 28, 99, 55, 32};
for (int i = 0; i < array.length - 1; i++) {
final int MIN_POS = array.length - 1 - i;
int MIN_VAL_POS = 0;
for (int j = 1; j <= MIN_POS; j++) {
if (array[j] < array[MIN_VAL_POS]) {
MIN_VAL_POS = j;
}
}
if (MIN_VAL_POS != MIN_POS) {
int temp = array[MIN_VAL_POS];
array[MIN_VAL_POS] = array[MIN_POS];
array[MIN_POS] = temp;
}
}
}
原理：
- 外部循环从数组的第一个元素开始，一直迭代到倒数第二个元素。
- 初始化最小位置：在每一次外部迭代开始时，都定义一个常量
MIN_POS，表示当前未排序部分的最后一个位置。 - 查找最小值位置：内部的for循环用于在未排序部分查找最小元素。
- 一旦内部循环完成，我们检查
MIN_VAL_POS是否等于MIN_POS。如果它们不相等，说明找到了一个更小的元素，需要将这个元素与未排序部分的第一个元素进行交换，以确保最小元素放在已排序部分的末尾。
3. 冒泡排序
升序：
public static void main(String[] args) {
int[] array = {14, 98, 36, 80, 28, 99, 55, 32};
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
降序：
public static void main(String[] args)
{
int[] array = {14,98,36,80,28,99,55,32};
for(int i = 0 ; i < array.length-1 ; i++)
{
for(int j = 0 ; j < array.length-1-i ; j++)
{
if(array[j] < array[j+1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
原理：
- 外部循环：控制了遍历的轮数
- 内部循环：内部的
for循环用于比较相邻的元素并且交换他们的位置，每一轮都会将未排序部分的最大元素移动到正确的位置。
4.桶排排序(此处介绍一种特殊的桶排排序——基数排序)
升序：
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] > max)
max = array[i];
}
int size = 1;
while((max/=10)>=1)
size++;
//记录某数位值的数量（一维）
int [] ixs = new int [10];
//统计对应数位值的元素（二维）
int [][] vals = new int [10][array.length];
//从低位到高位：
for (int i = 0; i < size; i++) {
//1.按数位值提取 计算数位值数量并存放在一维数组中 并将元素存放在二维数组中
for (int k = 0; k < array.length; k++) {
int t = (array[k]/(int)Math.pow(10,i))%10;
vals[t][ixs[t]++] = array[k];
}
//2.将二维数组中的元素按数位值放回array 两层循环（放回的循环方向决定了升降序）
for (int m = 0 , n = 0; m < ixs.length; m++) {
for (int j = 0; j < ixs[m]; j++) {
array[n++] = vals[m][j];
}
}
//3.ixs数组的清零
for (int j = 0; j < ixs.length; j++) {
ixs[j] = 0;
}
}
降序：
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] > max)
max = array[i];
}
int size = 1;
while((max/=10)>=1)
size++;
//记录某数位值的数量（一维）
int [] ixs = new int [10];
//统计对应数位值的元素（二维）
int [][] vals = new int [10][array.length];
//从低位到高位：
for (int i = 0; i < size; i++) {
//1.按数位值提取 计算数位值数量并存放在一维数组中 并将元素存放在二维数组中
for (int k = 0; k < array.length; k++) {
int t = (array[k]/(int)Math.pow(10,i))%10;
vals[t][ixs[t]++] = array[k];
}
//2.将二维数组中的元素按数位值放回array 两层循环（放回的循环方向决定了升降序）
for (int m = 0 , n = array.length; m < ixs.length; m++) {
for (int j = 0; j < ixs[m]; j++) {
array[--n] = vals[m][j];
}
}
//3.ixs数组的清零
for (int j = 0; j < ixs.length; j++) {
ixs[j] = 0;
}
}
原理：
1. 分布元素到桶中：根据元素的特定属性将它们分配到不同的桶中。
2. 单独排序每个桶
3. 合并桶：将每个桶中已排序的元素合并成一个单一的、有序的数组。
基数排序原理：
假设随机生成的数组 array 如下所示：
int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
1.找出最大值，确定最大值的数位
最大值为`802`，因此，最大位数为`3`(802是一个三位数)
int size=1;
while((max/=10)>=1) size++;
2.从低位到高位进行排序(分桶并对桶单独排序)
第一轮排序 - 个位数
分配：根据个位数，将每个元素分配到相应的桶中。例如，170（个位是 0）会去到桶 0，45（个位是 5）会去到桶 5。
分配后的桶内容可能如下：
桶 0：170, 90
桶 1：无
桶 2：802, 2
桶 3：无
桶 4：24
桶 5：45, 75
桶 6：66
桶 7：无
桶 8：无
桶 9：无
收集：按照桶的顺序收集元素，得到新的数组。新数组是：170, 90, 802, 2, 24, 45, 75, 66。
第二轮排序 - 十位数
分配：现在基于十位数进行分配。例如，802（十位是 0）会去到桶 0，75（十位是 7）会去到桶 7。
分配后的桶内容可能如下：
桶 0：802, 2
桶 1：无
桶 2：24
桶 3：无
桶 4：45
桶 5：无
桶 6：66
桶 7：75
桶 8：无
桶 9：90, 170
收集：收集元素，新数组是：802, 2, 24, 45, 66, 75, 90, 170。
第三轮排序 - 百位数
分配：最后，根据百位数分配。例如，802（百位是 8）会去到桶 8，24（没有百位，视为 0）会去到桶 0。
分配后的桶内容可能如下：
桶 0：2, 24, 45, 66, 75, 90, 170
桶 1：无
桶 2：无
桶 3：无
桶 4：无
桶 5：无
桶 6：无
桶 7：无
桶 8：802
桶 9：无
收集：最终收集元素，得到排序后的数组：2, 24, 45, 66, 75, 90, 170, 802。
5.计数排序
升序：
//找出最大值和最小值 并求出最大数组长度构建数组
for (int j = 1; j < num; j++) {
if (array[j] > max)
max = array[j];
if (array[j] < min)
min = array[j];
}
//找出数组元素与数组下标的关系并对应
int[] tempArr = new int[max - min + 1];
for (int v : array) {
tempArr[v - min]++;
}
//通过下标 得出某数组元素的重复个数（循环1）并按序输出（循环2）
System.out.print("[");
for (int m = 0; m < tempArr.length; m++)//控制升降序的地方
{
for (int n = 0; n < tempArr[m]; n++) {
System.out.print(min + m);
if(m== tempArr.length-1&&n==tempArr[tempArr.length-1]-1)
System.out.println("]");
else
System.out.print(",");
}
}
降序：
//找出最大值和最小值 并求出最大数组长度构建数组
for (int j = 1; j < num; j++) {
if (array[j] > max)
max = array[j];
if (array[j] < min)
min = array[j];
}
//找出数组元素与数组下标的关系并对应
int[] tempArr = new int[max - min + 1];
for (int v : array) {
tempArr[v - min]++;
}
//通过下标 得出某数组元素的重复个数（循环1）并按序输出（循环2）
System.out.print("[");
for (int m = tempArr.length-1;m>=0;m--)//控制升降序的地方
{
for (int n = 0; n < tempArr[m]; n++) {
System.out.print(min + m);
if(m==0&&n==tempArr[tempArr.length-1]-1)
System.out.println("]");
else
System.out.print(",");
}
}
原理：
- 找到最大值和最小值
- 创建计数数组
tempArr[max-min+1]，确保可以覆盖所有可能的值，每个索引对应输入数组中所有可能出现的整数值。 - 计数：遍历原始数组，对每个元素出现的次数进行计数。
- 输出排序结果：遍历
tempArr数组，对于数组中的每个元素tempArr[m]，输出min+m这个值tempArr[m]次。
6.希尔排序
升序：
int size = num;
while((size/=2)>=2)
{
for (int j = 0; j < array.length-size; j++)
{
if(array[j] > array[j+size])//控制升降序的地方 1
{
int temp2 = array[j];
array[j] = array[j + size];
array[j + size] = temp2;
}
}
}
//再进行排序
for(int m,k = 1; k < array.length ;k++)
{
int temp3 = array[k];
for(m = k-1 ; m>=0&&array[m]>temp3 ; m--)//控制升降序的地方 2
{
array[m+1] = array[m];
}
array[m+1] = temp3;
}
降序：
int size = num;
while((size/=2)>=2)
{
for (int j = 0; j < array.length-size; j++)
{
if(array[j] < array[j+size])//控制升降序的地方 1
{
int temp2 = array[j];
array[j] = array[j + size];
array[j + size] = temp2;
}
}
}
//再进行排序
for(int m,k = 1; k < array.length ;k++)
{
int temp3 = array[k];
for(m = k-1 ; m>=0&&array[m]<temp3 ; m--)//控制升降序的地方 2
{
array[m+1] = array[m];
}
array[m+1] = temp3;
}
原理:
- 核心思想是
使数组中任意间隔为h的元素都是有序的 - 希尔排序的间隔序列，代码通过一个
while循环来控制排序的间隔size，间隔size是通过不断将数组长度除以2来获取的，直至这个间隔变成2以下。
对于size的每一个值，代码通过一个 for 循环遍历数组。如果找到两个间隔为 size 的元素是逆序|升序的，则交换这两个元素。
随着size的减小，数组会越来越趋近于完全排序。 - 最终再进行一次插入排序。
7.快速排序
升序：
public class QuickSort {
public Random rand;
public void swap(int[] nums, int l, int r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
public void pivot(int[] nums, int l, int r) {
/**
* 归并终止条件
*/
if (l >= r) {
return;
}
/**
* 下标范围[l,r]
*/
int mid = rand.nextInt(r - l + 1) + l;
swap(nums, l, mid);
int
x = nums[l],
i = l + 1,
j = r;
/**
* 左边找到比x大的数字，i不动；右边找到比x小的数字，j不动，作值交换
*/
while (i < j) {
while (i < j && nums[i] < x) {
i++;
}
while (i < j && nums[j] > x) {
j--;
}
swap(nums, i, j);
}
/**
* i,j重合了，x应该与哪个下标的值作交换？
*/
if (nums[i] <= x) {
swap(nums, l, i);
} else {
swap(nums, l, i - 1);
i--;
}
/**
* 对pivot(下标为i)的两侧进行递归排序
*/
pivot(nums, l, i - 1);
pivot(nums, i + 1, r);
}
public int[] quickSortArr(int[] nums) {
/**
* 在对排序进行包装的同时实现Random类
*/
rand = new Random(System.currentTimeMillis());
pivot(nums, 0, nums.length - 1);
return nums;
}
}
降序：
public class QuickSort {
public Random rand;
public void swap(int[] nums, int l, int r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
public void pivot(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int mid = rand.nextInt(r - l + 1) + l;
swap(nums, l, mid);
int x = nums[l],
i = l + 1,
j = r;
while (i < j) {
// 修改为找到比x小的数字停止，以便进行降序排列
while (i < j && nums[i] > x) {
i++;
}
// 修改为找到比x大的数字停止，以便进行降序排列
while (i < j && nums[j] < x) {
j--;
}
swap(nums, i, j);
}
if (nums[i] >= x) { // 修改条件以确保降序排列
swap(nums, l, i);
} else {
swap(nums, l, i - 1);
i--;
}
pivot(nums, l, i - 1);
pivot(nums, i + 1, r);
}
public int[] quickSortArr(int[] nums) {
rand = new Random(System.currentTimeMillis());
pivot(nums, 0, nums.length - 1);
return nums;
}
}
原理：
- 选择基准：可以随机选取一个元素作为基准
- 分区：重新排列数组，使所有小于基准的元素都移动到基准的左边，而所有大于基准的元素都移动到基准的右边。
- 递归排序子数组：递归地将上述过程应用于基准左侧和右侧地子数组
8.归并排序
升序：
public static void mergeSort(int[] nums){
mergeSort(nums,0,nums.length-1);
}
public static void mergeSort(int[] nums,int start,int end){
if(start < end){
int mid = start + (end-start)/2;
mergeSort(nums,start,mid);
mergeSort(nums,mid+1,end);
merge(nums,start,mid,end);
}
}
private static void merge(int[] nums,int start,int mid,int end){
int
p1 = start,
p2 = mid+1,
count = 0;
int[] temp = new int[end-start+1];
while(p1<=mid && p2<=end){
if(nums[p1] < nums[p2]){
temp[count] = nums[p1];
p1++;
}else{
temp[count] = nums[p2];
p2++;
}
count++;
}
while(p1<=mid){
temp[count++] = nums[p1++];
}
while(p2<=end){
temp[count++] = nums[p2++];
}
for (int i = 0; i < temp.length; i++) {
nums[i+start] = temp[i];
}
}
降序：
public static void mergeSort(int[] nums){
mergeSort(nums,0,nums.length-1);
}
public static void mergeSort(int[] nums, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
}
private static void merge(int[] nums, int start, int mid, int end) {
int p1 = start, p2 = mid + 1, count = 0;
int[] temp = new int[end - start + 1];
while (p1 <= mid && p2 <= end) {
if (nums[p1] > nums[p2]) { // 修改比较逻辑，以降序排列
temp[count] = nums[p1];
p1++;
} else {
temp[count] = nums[p2];
p2++;
}
count++;
}
while (p1 <= mid) {
temp[count++] = nums[p1++];
}
while (p2 <= end) {
temp[count++] = nums[p2++];
}
for (int i = 0; i < temp.length; i++) {
nums[i + start] = temp[i];
}
}
原理：
- 将数组从中间分割成两个子数组，继续递归地将这些子数组分割，直至每个子数组只包含一个元素。
- 逐步合并这些子数组。
排序算法的时间复杂度分析
-
插入排序（Insertion Sort）
- 最好情况时间复杂度：
O(n) - 平均情况时间复杂度：
O(n²) - 最坏情况时间复杂度：
O(n²) - 空间复杂度：
O(1)
- 最好情况时间复杂度：
-
选择排序（Selection Sort）
- 最好情况时间复杂度：
O(n²) - 平均情况时间复杂度：
O(n²) - 最坏情况时间复杂度：
O(n²) - 空间复杂度：
O(1)
- 最好情况时间复杂度：
-
冒泡排序（Bubble Sort）
- 最好情况时间复杂度：
O(n) - 平均情况时间复杂度：
O(n²) - 最坏情况时间复杂度：
O(n²) - 空间复杂度：
O(1)
- 最好情况时间复杂度：
-
桶排序（Bucket Sort）
- 最好情况时间复杂度：
O(n+k) - 平均情况时间复杂度：
O(n+k) - 最坏情况时间复杂度：
O(n²) - 空间复杂度：
O(n+k)
- 最好情况时间复杂度：
-
计数排序（Counting Sort）
- 最好情况时间复杂度：
O(n+k) - 平均情况时间复杂度：
O(n+k) - 最坏情况时间复杂度：
O(n+k) - 空间复杂度：
O(k)
- 最好情况时间复杂度：
-
希尔排序（Shell Sort）
- 最好情况时间复杂度：取决于间隔序列
- 平均情况时间复杂度：取决于间隔序列，一般认为是
O(nlogn) - 最坏情况时间复杂度：取决于间隔序列
- 空间复杂度：
O(1)
-
快速排序（Quick Sort）
- 最好情况时间复杂度：
O(nlogn) - 平均情况时间复杂度：
O(nlogn) - 最坏情况时间复杂度：
O(n²) - 空间复杂度：取决于实现方式，一般为
O(logn)（递归实现时）
- 最好情况时间复杂度：
-
归并排序（Merge Sort）
- 最好情况时间复杂度：
O(nlogn) - 平均情况时间复杂度：
O(nlogn) - 最坏情况时间复杂度：
O(nlogn) - 空间复杂度：
O(n)
- 最好情况时间复杂度：
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
22
0- 0
已为社区贡献4条内容
所有评论(0)