排序总结
1.序
从今天开始我分模块推出面试指南，首先作为程序员最重要的是数据结构，数据结构是我们的本科课程，同时也是我们的必备课程。排序是我们的必考内容，今天以排序算法引出我们的数据结构。
2.总
结论：快速排序 > 归并排序 > 希尔排序 > 堆排序
3 交换排序
冒泡排序
根据序列中两个记录的值的比较结构来交换两个记录在序列中的位置，将值较小的向前移动
特点：算法的本质是减治排序
时间复杂度：
- 最好情况（正序）：O（n）
- 最坏情况（逆序）：O(n2)
- 平均情况：O(n2)
空间复杂度：O(1)
稳定性：稳定
/**
* @Author liuhaidong
* @Description 冒泡排序
* @Date 14:35 2019/10/2 0002
*/
private static void BubbleSort(int[] source) {
int tmp = 0;
for(int i =0;i<source.length;i++){
for (int j =0;j<source.length-1-i;j++){
if(source[j]>source[j+1]){
tmp = source[j+1];
source[j+1] = source[j];
source[j] = tmp;
}
}
}
// //方法二
// int tmp = 0;
// for(int i=0;i<arr.length-1;i++){
// for(int j=arr.length-1;j>i;j--){
// //进行交换
// if(arr[j] <arr[j-1]){
// tmp = arr[j];
// arr[j] = arr[j -1];
// arr[j-1] = tmp;
// }
// }
// }
}
快速排序
一共包含三大步：
1.确定待排序元素序列中的某元素作为基准值（选区间最右边的元素/选中间元素 与最右边的元素交换）
2.以基准值为界，大于基准值的放在基准值的右边，小于基准值的放在基准值左边(hover 挖坑 前后下标)
3.然后对左右序列重复该过程，直到小区间中只有一个元素或没有元素为止（size==0||size ==1）
特点：采用分治算法
时间复杂度：
最好情况：O(n*long(n)) （区间分割，组成形式可以考虑为二叉树形式，最好情况就成了单支树，分治算法变成了减治算法）
平均情况：O(n*long(n))
最差情况：O（n2）
空间复杂度：O(log(n))—O（n）
稳定性：不稳定
/**
* @Author liuhaidong
* @Description快速排序
* @Date 15:51 2019/10/2 0002
*/
private static void QuickSort(int[] arr, int low, int high) {
if(low < high){
// 找寻基准数据的正确索引
int index = GetIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
QuickSort(arr, 0, index - 1);
QuickSort(arr, index + 1, high);
}
}
private static int GetIndex(int[] arr, int low, int high) {
int i = low, j = high;
int x = arr[low];
//s[l]即s[i]就是第一个坑
while (i < j)
{
// 从右向左找小于x的数来填s[i]
while(i < j && arr[j] >= x){
j--;
}
if(i < j)
{
arr[i] = arr[j];
//将s[j]填到s[i]中，s[j]就形成了一个新的坑
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && arr[i] < x)
{
i++;
}
if(i < j)
{
arr[j] = arr[i];
//将s[i]填到s[j]中，s[i]就形成了一个新的坑
j--;
}
}
//退出时，i等于j。将x填到这个坑中。
arr[i] = x;
return i;
}
4 插入排序
直接插入排序
将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，就得到一个新的序列。（抓扑克牌思想）
特点：元素越接近有序，直接插入排序算法的时间效率越高，算法的本质是减治算法；因此当数组接近有序或大概率有序的情况下，或是数组的数量比较小的时候采用插入排序。
时间复杂度：
最好情况：（有序且为正序）O(n)
最坏情况：（逆序）O(n^2）
平均情况：O(n2)
空间复杂度：O(1)
具有稳定性
/**
* @Author liuhaidong
* @Description 直接插入排序
* @Date 16:29 2019/10/2 0002
*/
private static void InsertSort(int[] arr) {
int tmp = 0;
int i ,j;
for(i = 1; i < arr.length; i++) {
/**
* temp为本次循环待插入有序列表中的数
*/
tmp = arr[i];
for(j = i-1;j >=0 && arr[j] > tmp;j--)
{
/**
* 元素后移，为插入temp做准备
*/
arr[j+1] = arr[j];
}
/**
* 插入temp
*/
arr[j+1] = tmp;
}
}
希尔排序
先将数据进行分组，通过插入排序的方式让数据基本有序，然乎再进行插入排序，能够让插入排序最坏情况的概率降低；
分组的方法：固定步长取值分为一组的方法。分组越多（步长越小）大的数往后走的越快，分组越少排完后越接近有序
希尔排序是对直接插入排序的优化
时间复杂度：
最好情况（正序）：O（n）
平均情况：O(n1.3–n2)
最坏情况（逆序）：O(n2)
空间复杂度：O(1)
不具有稳定性的排序
/**
* @Author liuhaidong
* @Description 希尔排序
* @Date 16:46 2019/10/2 0002
*/
private static void ShellSort(int[] arr) {
//初始化一个间隔
int h = 1;
//计算最大间隔
while(h < arr.length / 3) {
h = h * 3 + 1;
}
while(h > 0) {
//进行插入排序
int tmp = 0;
for(int i = h; i < arr.length; i++) {
tmp = arr[i];
int j = i;
while(j > h - 1 && arr[j - h] >= tmp) {
arr[j] = arr[j - h];
j -= h;
}
arr[j] = tmp;
}
//减小间隔
h = (h - 1) / 3;
}
}
5 选择排序
选择排序
每一次从待排序的元素中选出最小的一个元素，若它不是这组元无序素中的最后一个元素，则将它与存放这组有序元素的起始位置交换，直到全部待排序元素全部排完。
或是从无序元素中选出一个最大的，若其不是无序区间的最后一个元素，则将其与存放有序区间的最后一个元素交换，直到无序元素全部排完
特点：效率不高，算法的本质是减治算法
时间复杂度：
最好情况：O(n2)
平均情况：O(n2)
最坏情况：O(n2)
空间复杂度：O（1）
稳定性：不稳定
/**
* @Author liuhaidong
* @Description 选择排序
* @Date 17:10 2019/10/2 0002
*/
private static void SelectionSort(int[] arr) {
int k =0;
int tmp = 0;
for(int i = 0;i<arr.length-1;i++){
k = i;
for(int j =i+1;j<arr.length;j++){
if(arr[j] <arr[k]){
k = j;
}
}
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
}
堆排序
利用堆的特点设计的一种排序算法，排升序要建大堆，排降序要建小堆，建堆是从第一个非叶子节点开始建，利用向下调整的思想逐步建立出整个堆
每次将未排序序列的第一个与最后一个元素进行交换，然后利用向下调整，将最大的元素调整到最后一个。
特点：算法的本质是减治算法
时间复杂度：
最好情况：O（n*longn）
平均情况：O（n*longn）
最坏情况：O（n*longn）
空间复杂度：O(1)
稳定性：不稳定
/**
* @Author liuhaidong
* @Description 堆排序
* @param
* @Date 20:30 2019/10/2 0002
*/
private static void HeadSort(int[] arr) {
int startIndex = (arr.length-1)/2;
//定义开始调整的位置
for(int i =startIndex;i>=0;i--){
ToMaxHeap(arr,arr.length,i);
//调整成大顶堆的方法
}
//经过上面的操作后，已经把数组变成一个大顶堆，把根元素和最后一个元素进行调换
for(int i = arr.length-1;i>0;i--){
int t = arr[0];
arr[0] = arr[i];
arr[i] = t;
//进行调换
ToMaxHeap(arr,i,0);
//换完之后我们再把剩余元素换成大顶堆
}
}
/**
* @Author liuhaidong
* @Description
* @param //arr要排序的数组 size调整元素的个数 index从哪里开始调整
* @Date 19:38 2019/10/2 0002
*/
private static void ToMaxHeap(int[] arr, int size, int index) {
int leftNodeIndex = index * 2 + 1;
int rightNodeIndex = index * 2 + 2;
//获取左右字节的索引
int maxIndx = index;
if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxIndx]) {
maxIndx = leftNodeIndex;
}
if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxIndx]) {
maxIndx = rightNodeIndex;
}
//查找最大节点所对应的索引
if (maxIndx != index) {
int t = arr[maxIndx];
arr[maxIndx] = arr[index];
arr[index] = t;
//调换完成后，可能会影响到下面的子树，不是大顶堆，我们还需要再次调整
ToMaxHeap(arr, size, index);
}
}
6 归并排序
把数组平均分成两部分，分别对左右两部分做均分，直到区间的size<=1，然后利用一个额外的数组空间，逐步将两个数组按序排列，再将排好的数据拷贝回原始数组，这样使子序列的段间有序，将子序列归并为完整的序列
特点：分治算法，是外部排序最好的算法
时间复杂度：
最好情况：O（n*log(n)）
空间复杂度：O（n）
稳定性：稳定
需要做外部排序的情况：
1.内存放不下了，切成小块，将每一小块排序，然后合并n个有序数组
/**
* @Author liuhaidong
* @Description 归并排序
* @param
* @Date 21:48 2019/10/2 0002
*/
private static void MergrSort(int[] arr) {
Split(arr,0,arr.length-1);
//拆分 我们先给一个左右两边是有序的一个数组，先来进行归并排序 {4,5,7,8, 1,2,3,6}
}
//进行拆分
private static void Split(int[] arr, int startIndex, int endIndex) {
//计算中间索引
int centerIndex = (startIndex + endIndex)/2;
if(startIndex < endIndex){
Split(arr, startIndex, centerIndex);
Split(arr, centerIndex+1, endIndex);
Mergr(arr,startIndex,centerIndex,endIndex);
//进行归并
}
}
//进行归并
private static void Mergr(int[] arr, int startIndex, int centerIndex, int enIndex) {
int[] tempArr = new int[enIndex-startIndex+1];
//定义一个临时数组
int i = startIndex;
//定义一个左边数组的起始索引
int j = centerIndex+1;
//定义一个右边数组的起始索引
int index = 0;
//定义一个临时数组的起始索引
while (i <= centerIndex && j<=enIndex){
//比较左右两个数组的元素大小，往临时数组中放
if(arr[i] <= arr[j]){
tempArr[index] = arr[i];
i++;
}else {
tempArr[index] = arr[j];
j++;
}
index++;
}
//处理剩余元素 可能是左边元素，也可能是右边元素
while(i <= centerIndex){
tempArr[index] = arr[i];
i++;
index++;
}
while(j <= enIndex){
tempArr[index] = arr[j];
j++;
index++;
}
for(int k = 0;k<tempArr.length;k++){
arr[k+startIndex] = tempArr[k];
}
}
7 函数主体
public static void main(String[] args) {
int i = 100000;
//记录开始测试的数量
// int n = 100_000_000;
// //记录最大的测试量
// int step = 10_000_000;
// //记录每一次数据累加量
int num = 1;
//记录当前测试次数
long s = 0;
//记录开始时间
long e = 0;
//记录结束时间
//for(;i<n;i+= step){
int[] source = new int[i];
int[] result = new int[i];
for (int j = 0; j < i; j++) {
source[j] = new Random().nextInt() % i;
}
//生成随机数
System.out.println("---------------------------第 "+ num++ +" 次，数据量：" + i + "----------------------------");
//冒泡排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
BubbleSort(result);
e = System.currentTimeMillis();
System.out.println("冒泡排序时间：" + (e - s));
//快速排序******************************************
// System.arraycopy(source, 0, result, 0, source.length);
// s = System.currentTimeMillis();
// QuickSort(result,0,result.length-1);
// e = System.currentTimeMillis();
// System.out.println("快速排序时间：" + (e - s));
//插入排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
InsertSort(result);
e = System.currentTimeMillis();
System.out.println("插入排序时间：" + (e - s));
//希尔排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
ShellSort(result);
e = System.currentTimeMillis();
System.out.println("希尔排序时间：" + (e - s));
//选择排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
SelectionSort(result);
e = System.currentTimeMillis();
System.out.println("选择排序时间：" + (e - s));
//堆排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
HeadSort(result);
e = System.currentTimeMillis();
System.out.println("堆排序时间：" + (e - s));
//归并排序******************************************
System.arraycopy(source, 0, result, 0, source.length);
s = System.currentTimeMillis();
MergrSort(result);
e = System.currentTimeMillis();
System.out.println("归并排序时间：" + (e - s));
//}
}
京公网安备 11010502036488号