1.冒泡排序
- 交换排序的一种
- 依次比较相邻的两个待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”
- 每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置
- 直到全部元素有序为止/直到某次冒泡过程中没有发生交换为止
思路
- 第一次循坏遍历整个数组，找到数组中最大的一个元素，让其和数组中第一个元素交换位置，a[0]=最大元素
- 第二次循坏遍历整个数组，找到数组中次最大一个元素，让其和数组中第二个元素交换位置，a[1]=次最大元素
- 以此类推，遍历完整个数组，
public void sort(int[] arr) {
int temp = 0;
for (int j = 0; j < arr.length; j++) {
for (int i = 0; i < arr.length - j - 1; i++) {
//如果前一个元素大于后一个元素，则需要交换2个位置的数据
if (arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
2.插入排序
思路
- 创建一个空数组，存放排序的数据
- 从原数组中依次选择的数据
- 在新数组中寻找插入点，
- 如该点没有数据，就将数据插入到该点。否则需把该插入点后面的所有数据向后移动一位，空出位置，插入数据。
public void sort(int[] arr) {
int cur,pIdx;
for(int i=1;i<arr.length;i++){
//基准元素
cur=arr[i];
pIdx=i-1;
//如果前一个元素大于基准点值，不断向前寻找插入点，
while(pIdx>=0 && arr[pIdx]>cur){
arr[pIdx+1]=arr[pIdx];
pIdx--;
}
arr[pIdx+1]=cur;
}
}
3. 希尔排序
- 缩小增量排序
- 其是插入排序的改进版，改进点：减少了插入排序时移动元素次数。
基本思想
先将整个待排记录序列分割为若干子序列分别进行直接插入排序，待整个序列的记录“基本有序”时，再对全体记录进行一次直接插入排序
public void sort(int[] arr) {
//gap=arr.length/2, gap以每次/2的方式递减
for(int gap=arr.length/2;gap>0;gap=gap/2){
//以gap元素开始，对gap中的一组数据进行排序
for(int i=gap;i<arr.length;i++){
int cur=i;
int temp=arr[cur];
if(arr[cur]<arr[cur-gap]){
while(cur-gap>=0 && temp<arr[cur-gap]){
arr[cur]=arr[cur-gap];
cur-=gap;
}
arr[cur]=temp;
}
}
}
}
4.快速排序
基本概念
- 就平均时间而言，快速排序是目前被认为最好的一种内部排序方法,由C. A. R. Hoare发明
- 分治法(divide and conquer)思想的体现
- Unix系统函数库所提供的标准排序方法
- C标准函数库中的排序方法直接就命名为qsort()
- 轴值(pivot):
- 书上称枢轴
- 用于将记录集”分割”为两个部分的那个键值
- 分割(partition):
- 将记录集分为两个部分,前面部分记录的键值都比轴值小,后面部分的键值都比轴值大
基本思想
是对冒泡排序的一种改进 选取一个轴值,然后根据此轴值通过一趟排序对记录集进行一次分割,然后对分割后产生的两个记录子集分别进行快速排序
@Override
public void sort(int[] arr) {
qSort(arr,0,arr.length-1);
}
private void qSort(int[] arr,int l,int r){
int i=l;
int j=r;
if(i>j){
return;
}
int temp=arr[l];
while(i!=j ){
//如果当前元素大于基准元素，指针向左移动一位，直到找到一个小于基准元素为止，此时记录下标
while(arr[j]>temp && i<j){
j--;
}
//如果当前元素小于基准元素，指针向右移动一位，直到找到一个大于基准元素为止，此时记录下标
while(arr[i]<=temp && i<j){
i++;
}
//交换2个下标的元素
if(i<j){
swap(arr,i,j);
}
}
swap(arr,l,i);
qSort(arr,l,i-1);
qSort(arr,i+1,r);
}
private void swap(int[] arr,int i, int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
5. 选择排序
基本思想
-
是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
-
==与冒泡排序不同点：减少了元素交换次数==
/**
* 选择排序算法，从小到大的方式开始排序
* <ul>
* 实现思路：
* <li>第一次循环找到数组的最小的一个元素，放在数组的第一个位置</li>
* <li>第二次循环找到数组中第二小的一个元素，放在数组的第二个位置 </li>
* <li>第三次循环找到数组中第三小的一个元素，放在数组的第三个位置</li>
* <li>以此类推，直到走完数组中所有元素</li>
* </ul>
* <strong>
* 与冒泡最大区别，交换元素次数会较少
* </strong>
* @param arr
*/
@Override
public void sort(int[] arr) {
int minIdx=0,temp=0;
for(int i=0;i<arr.length;i++){
//需要找到余下数组中最小的一个元素
minIdx=i;
for(int j=i+1;j<arr.length;j++){
//假设第一个元素是最小值，余下元素如果比第一个元素小，
// 记录小的元素下标，剩下元素再和这个最小元素比较，从而找到更小的元素
if(arr[j]<arr[minIdx]){
minIdx=j;
}
}
temp=arr[i];
arr[i]=arr[minIdx];
arr[minIdx]=temp;
}
}
6.计数排序
- 是一种基于非比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 一种牺牲空间换取时间的做法。
- 只适合数字类型的排序
基本思想
- 开启额外的空间，来存储数组中元素
- 旧数组种元素（数字）作为新数组的下表，并记录相同元素的个数
- 最后将新数组反向输出，从而得到有序的数组
/**
* 计数排序算法，从小到大的方式开始排序
* <ul>
* 实现思路：
* <li>只适合数字类型的排序 </li>
* <li>会开启额外的空间，来存储数组中元素</li>
* <li>旧数组种元素（数字）作为新数组的下表，并记录相同元素的个数</li>
* <li>最后将新数组反向输出，从而得到有序的数组</li>
* </ul>
* @param arr
*/
private void sort(int[] arr,int maxVal){
int[] newArr=new int[maxVal+1];
for(int i=0;i<arr.length;i++){
newArr[arr[i]]+=1;
}
int idx=0;
//反向输出数组种的元素
for(int i=0;i<newArr.length;i++){
int cnt=newArr[i];
while(cnt>0){
arr[idx++]=i;
cnt--;
}
}
}
7.桶排序
基本思想
将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
/**
* 桶排序算法，从小到大的方式开始排序
* <ul>
* 实现思路：将一个数组尽量拆分成一个个小数组（桶），在对桶里面元素进行排序，这个排序可以各种类型排序：插入，快排等等
* 和计数排序不同：计数排序只能用于数字，每个元素作为新数组下标
* </ul>
* @param arr
*/
@Override
public void sort(int[] arr) {
bucketSort(arr);
}
private void bucketSort(int[] arr){
int minVal=arr[0];
int maxVal=arr[0];
//求出数组中最大值和最小值
for(int i=0;i<arr.length;i++){
if(arr[i]<minVal){
minVal=arr[i];
}else if(arr[i]>maxVal){
maxVal=arr[i];
}
}
//桶数
int bucketNum = (maxVal - minVal) / arr.length + 1;
//创建一个二维数组存放桶和桶中的元素
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i = 0; i < arr.length; i++){
//这样分法，尽量保证每个桶中分到元素，尽量的少
int num = (arr[i] - minVal) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
//最后输出桶种元素
System.out.println(bucketArr.toString());
}
8.归并排序
基本思想
- 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)
-
思路
- 分阶段
- 类似于二分查找：将一个大数组折半拆分成二个数组
- 再对这2个数组进行折半拆分4个小数组
- …
- 直到小数组（长度=1）不可以再拆分
- 最后交换左右2个子数组来排序
- 治阶段
- 将2个子数组合并为一个有序数组
- 创建一个临时temp数组，长度为2个子数组长度和
- 最终完成2个子数组的合并
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
9.堆排序
基本思想
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
- 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
构造堆基本思路