# 排序算法

**Repository Path**: wkq-algorithm-library/sorting-algorithm

## Basic Information

- **Project Name**: 排序算法
- **Description**: 基于比较的排序算法汇总
选择排序法
插入排序法
归并排序法
快速排序法
堆排序法
冒泡排序法
希尔排序法
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-03-08
- **Last Updated**: 2024-03-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 七大基于比较的排序算法汇总
基于比较的排序算法汇总，这些排序算法之所以能够将元素进行排序 ，依赖于元素和元素之间的比较，以下的数组元素类型都需要实现Comparable接口。 
#### 介绍


##### [选择排序法](./src/com/wkq/selectionsort/SelectionSort.java)
算法思想：每次处理还没处理元素里最小的元素   

##### [插入排序法](./src/com/wkq/insertionsort/InsertionSort.java)

##### 归并排序法： O(nlogn)求解数组中逆序对个数   

* 自顶向下的归并排序法   

* 自底向上的归并排序法   

##### 快速排序法：随机算法   O(n)求解selectK,topK 问题   

* 单路快速排序法: 如果数据中包含大量重复元素的话，也会退化成一个O(n^2)级别的算法，快速排序法不应该采用单路快速排序法   

* 双路快速排序法：   

* 三路快速排序法：    

##### 堆排序法 ： 堆；优先队列，求解selectK,topK 问题   

* 把所有的数据都扔进一个堆中，再依次从堆中取出这些数据，取出来的过程其实就已经排好序了，但是这样做空间是O(n)的   

* 可以通过Heapify在原地进行堆排序，这样空间不仅变成了O(1)级别，在性能上也变优了一些  
 
##### [冒泡排序法](./src/com/wkq/bubblesort/BubbleSort.java)   
O(n^2)的排序算法   
基本思想：每次比较相邻的两个元素   
第i轮开始，arr[n-i,n)已经排好序       
第i轮：通过冒泡在arr[n-i-1]位置上放上合适的元素    
第i轮结束：arr[n-i-1,n)已排好序      
##### [希尔排序法](./src/com/wkq/shellsort/ShellSort.java)： 分组的思想   
基本思想：让数组越来越有序，不能只处理相邻的逆序对           
对元素间距为n/2的所有数组做插入排序    
对元素间距为n/4的所有数组做插入排序    
对元素间距为n/8的所有数组做插入排序    
...    
对元素间距为1的所有数组做插入排序    

![基于比较的排序算法总结](https://images.gitee.com/uploads/images/2022/0308/215017_f51296ae_8411299.png "屏幕截图.png")