带你手撕排序算法(手撕排序算法)

java8

帖子摘要：文章目录 前言一、排序的相关概念二、插入排序1.直接插入1算法思想2算法讲解3代码及解析4代码总结   2.希尔排序( 缩小增量排序 )1算法思想2算法讲解3代码及其解析4代码总结    三、选择排序......

& ^* D+ [, {" o: C大家好，欢迎来到Java吧（www.java8.com），交流、学习Java技术、获取Java资源无任何套路，今天说一说：“带你手撕排序算法”

9 \- b" Z% o+ I* A, b
/ |$ B' a1 A9 i) ^        
8 q! b" u* E- }               
                    
; m1 T6 ?6 S% q4 g) K/ F: T                        
& ?5 k) j. |+ N7 x1 y                    
                    
) z! h  a7 N3 |4 c1 y. _- {+ } 文章目录
$ A8 ^* f8 h* E$ H

前言

一、排序的相关概念

二、插入排序

1.直接插入

1算法思想

2算法讲解

3代码及解析

4代码总结
   

2.希尔排序( 缩小增量排序 )

1算法思想

2算法讲解

3代码及其解析

4代码总结
  
  

三、选择排序改进版

1.直接选择排序

1算法思想

2算法讲解

3算法注意事项

4代码及解析

5算法总结
   

2.堆排序

1堆的介绍

2算法思想

3算法讲解

4代码及解析

5时间复杂度讲解

6算法总结
  
* U3 b1 Z% Z7 D9 v9 j  

三、交换排序

1.冒泡排序

1算法思想

2算法讲解

3算法代码

4算法总结
7 s: w  M" A3 [% C% \   

2.快速排序

(1)算法思想

2挖坑法

3左右指针法不建议使用

4前后指针法

5总代码及解析

6注意事项及改进

7算法总结
  
  

三、归并排序

1.归并排序

1算法思想

2算法讲解

(3)代码及解析

4算法总结
, T# O5 k7 N7 w. e) N8 Q: r$ p  
, k4 F8 G2 d& X" w* z  

总结


, P0 y( g1 Y0 d( j

0 b" v: Y# A5 s1 T前言
! K) g3 c6 y) E1 N- M) l鸽了好久了希望大家能够理解排序算法的学习和码文确实挺费时间的,本篇文章重要讲解以下排序算法和其拓展其他排序以后会补充


/ G- J. h( o, k1 m0 j

+ F" i4 j6 [+ r( J一、排序的相关概念
概念提前说明一下方便大家理解后续文章
2 t& _. W( i1 J
2 Q4 R4 O, n5 o  H) ]; O

排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起
8 |4 Y1 H2 C- T8 [" N: P3 B  L 来的操作

稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记
录的相对次序保持不变即在原序列中r=r[j]且r在r[j]之前而在排序后的序列中r仍
2 g1 ]4 i1 h. K6 L7 B' P 在r[j]之前则称这种排序算法是稳定的否则称为不稳定的

内部排序数据元素全部放在内存中的排序

外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据
$ m9 x+ ?9 X  x8 A8 { 的排序

2 r9 G1 N" f; Y二、插入排序
1.直接插入
1算法思想
9 ^' V! n7 |/ j; b
* \+ _1 b: \: V# i 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。实际中我们玩扑克牌时就用了插入排序的思想

# N/ B' a2 I- L+ M

* h' d, n6 c: v: Z: i+ g
2算法讲解

' N  d- x0 o7 W0 R, L
我们这里设排好了的数组的最后一位的位置为end设temp = a[end + 1]
9 O' r% R; ~1 C2 w



2 L# Y9 M8 Y! s1 F6 C+ }- M. F end+1=2, 2向前找比它小的数如果没找到或者已经到头了就将比他大的数全部为后面移动一位所以这里5位后面移动一位然后将已经保存在temp的2赋给啊a[end+1]
$ A$ p7 h1 t8 Y: [  N2 o) l$ A* X
% X8 k$ Z( s3 v+ Z# K2 R
可能有人说这种情况不典型好再讲一个比较典型的

; m8 j4 w: D9 j
: M  b0 X: L7 {: c" w5 o
; l- a0 c# Z* R. I# s) c. U7 z
' h3 o) z6 [8 z9 [* S) Y 这里3向前面找比他小的然后他找到了2在没找到之前讲4,56向移动一位在找到后将3赋给找到的数的前面一位
$ P0 y9 N( b$ B2 g% Q2 I( Q
/ c; K1 H  ?& d' P+ N8 Y
以下为完整过程
/ k0 Z. Z9 f3 G/ M# L7 y) B

7 X+ k5 h% E: n
3代码及解析

void InsertSort(int* a, int m)
  K1 K# B  i! S% r& G* \# k7 ~5 ?
{
1 j1 A& R1 _* }6 j& ~& g
        int i;
        for (i = 0; i 
5 q( I1 R, M0 J0 W$ X$ d
                int end = i;
( a4 m$ m, \3 [8 ~' W
                int temp = a[end + 1];
5 E' }% L  N# U# r: i4 K7 ^) C
                while (end >= 0)
& s7 ^3 b: q& m5 E2 M  j
                {
  i1 K) ^( G) P1 u8 Z
                        if (a[end] > temp)//这一步是将大于temp的数全部向后移动
, a' v2 o1 o; R% }
                        {
                                a[end + 1] = a[end];
                                end--;
                        }
6 Y# S% S* d0 J$ g5 y
                        else//找到比temp小的就直接退出                        
                        {
                                break;
1 h6 |6 c% f- x7 D
                        }        
" f6 N9 w0 j9 R7 w
                }
$ d4 s- |/ Y3 c. H& w; y) s
                a[end + 1] = temp;
        }
}
复制代码

0 o2 P8 L& H8 X9 ~4代码总结

; M7 ^+ H( S& e% z [ol]

元素集合越接近有序直接插入排序算法的时间效率越高

时间复杂度最坏情况为逆序时或者接近逆序时O(N^2)最好情况为升序时或者接近升序时O(N)

空间复杂度O(1)它是一种稳定的排序算法

稳定性稳定[/ol]
. S" B, A( O# q* e( d$ h
当接近有序时我们将比temp大的数移动的次数将会减少所以算法的效率更高因此我们就需要对原本的数据进行处理使得效率得以提升那就是希尔排序

2.希尔排序( 缩小增量排序 )
1算法思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达=1时所有记录在统一组内排好序
' K7 ]% C1 s8 \2 E

2算法讲解
这里放一张图基本就清楚了


% _& N7 ~& D- S! l 我们对其进行分组每组都用直接插入排序进行排序那么整体就接近有序了当gap=1时就是直接插入排序了
8 T1 l/ C, R" D" b' ?- Y5 C
9 P& r6 [9 q! F! Q

5 y+ M  V& B. l' L: {( o4 g
& I: o* |: U% M6 n, F3代码及其解析
可能有细心的小伙伴就发现了无非就是将插入排序的1改成了gap吗也确实是这样无非是在插入排序上加了一个while循环控制gap而已

void ShellSort(int* a, int m)
{
  F2 w/ N3 z3 n3 N  l# }
        int gap = m;
& y7 {6 i6 s  u
        while (gap > 1)
  N  s$ P4 \" @
        {
6 @6 w- V4 [% I2 C- @1 t
                gap = gap / 3 + 1;//这里加一就可以保证gap最后为1从而变成直接插入排序
                for (int i = 0; i 
; P+ j: q  D5 z+ q. B$ u
                        int end = i;
+ y' e- s& _' Q
                        int temp = a[end + gap];
3 n3 U& j! t5 b
                        while (end >= 0)
                        {
/ I) P+ i- u5 H0 X+ |( f6 g
                                if (a[end] > temp)
                                {
                                        a[end + gap] = a[end];
                                        end -= gap;
                                }
* B' ^+ V' M+ Z8 r/ A/ b
                                else
; j) _2 a( S) Z( i
                                {
$ t8 c+ l2 F! M
                                        break;
' R) j3 B$ n2 q
                                }
" v9 `: a; R6 F8 p3 {6 S/ I3 s
                        }
                        a[end + gap] = temp;
4 N6 N) g6 P$ W
                }
, U6 O6 e: M8 d% C& n
        }
3 ?# W( J3 T7 K/ P0 V# l
}
复制代码

& l4 [8 w$ i( Q" n2 C' U4代码总结
. j6 u4 o! k; M$ u
[ol]

希尔排序是对直接插入排序的优化。

当gap > 1时都是预排序目的是让数组更接近于有序。当gap == 1时数组已经接近有了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试对比。

希尔排序的时间复杂度不好计算需要进行推导推导出来平均时间复杂度 O(N1.3—N2

稳定性不稳定[/ol]
5 R5 H+ b! i0 ]/ m
, ^$ P' l# l& m! h2 E5 E8 ^0 K6 J三、选择排序改进版
, ~; z. H' _* q7 R$ V1.直接选择排序
  a: Q( R7 L/ C0 o% Z1算法思想
' s0 E' {6 p6 q' s
每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的
5 h" Q1 J. J( l! M8 j 数据元素排完


0 P2 I  Q3 Z4 N6 }5 V2算法讲解
. |; O; ^9 Z- X/ Y4 G9 b9 H  P
  `2 N" P+ W$ i4 m. I! N$ Q4 ^ maxi向前面找最大的数maxi记录最大的数的下标mini向前找最小的数mini记录最小的数的下标,然后将min与begin位置的值交换将max与end位置的值交换

7 V  a6 u1 B* S' }: I# |
+ t* o- l; _; H1 m0 d% b3 f* q

3算法注意事项
如果在maxi交换或者mini的交换过程中交换的值刚好出现在begin或者end那么就会出现bugbug有以下处理方法


4 n. c; w* E, g& k! p 你问我为什么手写哈哈哈手写的更加引人瞩目一点你要是说我字丑我就打洗你

- _+ `# C3 @" p4代码及解析

void SelectSort(int* a, int m)
) e9 A: L2 E& m7 o
{
        int begin = 0;
        int end = m - 1;
- m9 H7 w- n. }  h
        while (begin 
                int maxi = begin;
                int mini = begin;
5 s9 l" H! e0 K4 K
                for (int i = begin; i 
                        if (a[maxi] 
                                maxi = i;
                        }
* \; S& t  N; j9 y) n
                        if (a[mini] > a[i])
                        {
1 h$ Q2 z. ~+ U# C+ P
                                mini = i;
                        }
9 t9 L8 j% X2 Z* Y# z/ \. J" \
                }
                Swap(&a[end], &a[maxi]);
                if (mini == end)//这里不懂看注意事项
                {
# R7 x* `/ y" U6 W9 ]% J
                        mini = maxi;
4 X! S0 |2 D9 ]/ ^0 H+ K( o4 B( f
                }
                Swap(&a[begin], &a[mini]);
                begin++;
                end--;
        }
: O, j8 _  R% z$ J
}
4 O( b1 p/ `" J$ X/ t4 V- Y
复制代码

5算法总结

" d' I0 S+ G+ S7 N% n [ol]

直接选择排序思考非常好理解但是效率不是很好。实际中很少使用

时间复杂度传统O(N^2)改进的代码能到N*logN

空间复杂度O(1)

稳定性不稳定[/ol]
, O: R, w5 k5 a9 z
2.堆排序

8 J4 J5 t* v, b. A  x 堆排序就需要对前面的二叉树有一定的理解才能弄明白如果不懂的可以移步至我的前一篇文章
* c2 X- g" V- f; }8 L  c

$ S& p. [* Q* @+ P+ g1堆的介绍
一张图解决
9 u0 H$ U1 V" D) d& o, n$ G
! Q7 v$ L+ R1 @. p2 `, y6 f
) T8 D* m' m6 `3 x 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是

排升序要建大堆排降序建小堆。
复制代码

$ l( Y8 g* c  ?( J5 S+ [  }7 f
( D( s. @! H8 F7 G% ^. `- e
7 @8 M; ]; O& h. `4 K; W$ Z  Y& v
0 F# ~( ]4 p4 e& P. c/ V' g" z/ a2算法思想

堆排序主要用的是向下调整算法·向下调整算法建立在左右子树已经是大堆或者是小堆才能有用那么向下调整的思想是怎么实现的
如果我们是建大堆向下调整算法是将一个节点与其子节点的最大值比较比较如果子节点有比其大的就交换两者的值然后继续向下将交换的节点的子节点继续向下比直到叶子节点此算法有一个大前提就是子节点必须是大堆或者小堆
" _. Q3 j& v' O9 Y2 w; E0 r% X
1 ?, G- _0 \: j+ |  L, R
那么就有人问如果子节点不是大堆或者小堆怎么办我们可以从最底部不是叶子节点的位置开始因为叶子节点本身就身就是大堆或者小堆对每个每个节点都使用向下调整算法一直调到root节点那么一个堆就完成了然后最大的值放在最后然后继续对这个最大的数的前面的数建堆然后继续与未排序好的数组的交换将是不是就ok了呢这就是堆排序的思想总是搞出最大的数排在最后

+ e# Y1 Q% Y" B( q3算法讲解
我们拿这个二叉树讲

4 ^) O. I3 J2 i1 y1 c  E& K- H
- }. N2 Y. E* n' \8 }  Q/ m7 T 这里我们建大堆我们首先找到最后一个非叶子节点8然后用8比较其节点无需交换在到7这个节点其应该与9交换然后就到2其应该与6交换这是建堆的过程后面的交换过程我就不讲了
- z% T1 R7 j3 g) g
- b- r: r# E! m% G4 u
6 T2 P1 U" h; I+ h 然后看这图

" J$ W3 C7 m1 q

6 F, o  q! Y  Q4代码及解析
3 [8 Z. V5 P: ^

//向下调整代码父子关系不清楚的看堆的介绍
8 R5 o" r8 t: x6 o1 P- O( B5 l
void AdjustDown(int* a, int n, int root)
{
        int parent = root;
; }; i& `9 K* q! [; _& F" s
        int child = parent * 2 + 1;
. x  {, J; I4 Z, m7 V1 X
        while (child 
                if (child + 1  a[child])
' a9 k+ H3 J8 F, _; F  i3 X( ^! Z" u+ r
                {
                        ++child;
                }
3 l/ _9 @- L7 a! M* R  V# j) i
                if (a[child] > a[parent])
; S4 {1 w8 C3 ?
                {
$ _2 q: n2 q: @6 y
                        Swap(&a[child], &a[parent]);
                        parent = child;
1 E  ~/ u* ]5 q; f0 y$ G9 o6 h
                        child = parent * 2 + 1;
9 y* e0 T6 i2 x! t1 W; G
                }
; H' v7 A' m) E, c" x
                else
                {
+ F  k( v8 P5 O
                        break;
                }
        }
}
* A3 i8 R+ x! {" B; `' J0 D/ W
//堆排序算法
5 R' z- h! C, k9 c$ N& X: @
void HeapSort(int* a, int n)
% v* w7 h: ^: L2 F5 Y5 V2 v7 {
{
        
, x; K4 s" a; ]' D! z
        int i;
        int end = n - 1;
        //建堆将一个数组建成一个堆的样子
- b1 k2 q' D2 O9 `: }8 z6 X
        for (i = (n - 1 - 1) / 2; i >= 0; --i)
5 D4 M' D3 S  @6 ]
        {
2 l2 p" R" a8 e! y/ |! K; @- H
                AdjustDown(a, n, i);
/ E5 L  J4 C1 A% D2 \
        }
        //交换堆的root到最后然后将数组的大小减小然后继续向下用调整算法
" D$ ?  G7 x4 ?1 v. R
        while (end > 0)
- Y6 [& z; P+ \6 `! V) w$ v
        {
) Z8 t: P; F$ F3 H# M4 _7 P
                Swap(a, &a[end]);
$ P, M9 n! M- {
                end--;
                AdjustDown(a, end + 1, 0);//因为这个数组已经是一个堆了所以我们只需要对其用向下调整算法就行了
        }
}
6 b3 C5 H9 R) O7 j
复制代码

3 l; n3 V- s3 o; e6 b+ f$ e: a/ M9 ^5时间复杂度讲解
, F' X! E1 @3 V8 B4 ?1 F' \这个算法的时间复杂度不好求解所以我来讲解一下


有人问为什么用图因为图清晰明了忽略字说字丑的小心我打洗你
求堆排序的复杂度需要知道高中的数列的错位相减法自行了解
9 l; T9 k4 ^( W$ K" x/ ]9 P
0 e  E* ?: A9 `6 `
4 E, i7 X, }$ h0 V  e6 P
* \$ z' r- D( _6 G: \' t  M/ S
* y1 g0 `/ q9 e6 B" [' x6算法总结

[ol]

堆排序使用堆来选数效率就高了很多。

时间复杂度向下调整算法ON

空间复杂度O(1)

稳定性不稳定[/ol]

( T5 N2 I7 t1 a- s' T  Y! A7 d' h三、交换排序
: k9 X; f) O! p8 M基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排
序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。

7 W0 l; n9 h2 x1.冒泡排序
1算法思想
  ^+ Q% ]' `( q与水中的气泡上浮相似大的先上去小的后上去
* I$ L" U& i: ]% j
2算法讲解
一图解决



3算法代码
2 e& a3 o  s8 e4 P7 o# \这里偷下懒更加推荐各位去看我前面的文章这里对冒泡排序有更加深刻的解释冒泡排序改进
# {7 o+ Q! m5 c' t* X5 ]
, @: p3 b" w/ T( z7 u4算法总结
4 r7 Q6 D6 ]- I! A8 @
[ol]

冒泡排序是一种非常容易理解的排序

时间复杂度O(N^2)

空间复杂度O(1)

稳定性稳定[/ol]

2.快速排序
(1)算法思想
0 y7 g. p# {# N8 z1 n( K
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序
) m# N; A+ ^! Q& ? 元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有
" }$ ]8 ^7 s% I 元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所
5 @8 Y" f/ |7 w4 L) c 有元素都排列在相应位置上为止
% F. P0 Z. h. @" Z  ^
6 [/ S1 i  F( D# l8 H- f
9 E$ q3 ]' w9 d6 K, X7 b+ d
, O8 y. c$ k+ I( e
+ b" N% E. ]- ?5 m! ]
9 x2 I- e% j; z' L& S9 ?6 Y
! w7 O# k; S* O. d2挖坑法
/ V6 S) k0 ]5 _% D0 y
1 X8 n4 I9 n5 c, s9 l1 W 先设立一个key记录begin的值再在begin处设个坑pivot先让end从后往前找比key小的值找到了就将这个值放入坑中然后这个比key小的值就成为了坑然后用begin向后找比key大的值找到了就放入坑中重复上述过程最后begin和end相交这个位置就是key应该到的位置代码中的三数取中后面的改进方法会讲
: Z1 V4 Y) B0 l
: U+ ^% f- U" Z0 ^) n% {" M
5 S' z. I2 c* `7 B0 r/ U

//挖坑法
int PartSort1(int* a, int left, int right)
{
* G4 T/ S# P7 r) _
        int begin = left, end = right;
3 `6 J2 E8 ^( Y- h5 {* d' l
        int mid = GetMidIndex(a, left, right);//三数取中
* s/ ^& Y- ^3 }8 j! a- U
        Swap(&a[mid], &a[begin]);
        int key = a[begin];
( ^/ ?, V2 D1 {; ]2 B+ W' ]
        int pivot = begin;
        while (begin 
  F# b1 W* t. o/ B. l7 b+ \5 T" N- E
                while (begin = key)
5 W$ q. }) Z5 O+ ?: l
                {
                        end--;
                }
                a[pivot] = a[end];
                pivot = end;
                while (begin 
                        begin++;
                }
                a[pivot] = a[begin];
                pivot = begin;
" C( p! E: h9 Z
        }
* p2 B( s: V( C* c: k3 ^
        a[begin] = key;
2 t7 p3 H6 R$ ^- x3 l! x( k
        return pivot;
" [% L$ T9 z* S+ \8 D
}
# ?- j) `% {+ k+ R1 P* g6 \
复制代码

3左右指针法不建议使用
4 g; u$ k/ l+ M6 c8 d- v
) g9 G, L  q: t! E 先设立一个keyi用来记录begin用begin向后找比keyi大的值找到了就停下让end从后往前找比key小的值找到了就停下然后交换两者的值两者相遇的位置即是keyi的位置然后交换keyi位置的值和相遇位置的值
4 r6 Q" P+ x& R" J( F
) e' q6 B6 h+ n4 D# `

//左右指针法
int PartSort2(int* a, int left, int right)
{
        int mid = GetMidIndex(a, left, right);
/ D* i2 I4 s6 L9 K5 e
        Swap(&a[left], &a[mid]);
$ P  H  z1 f/ v1 b- i& a. W
        int begin = left, end = right;
1 U) H2 h6 P# q1 W6 s
        int keyi = begin;
        while (begin 
- f0 Y' Z5 l( N, j# J
                while (begin = a[keyi])
0 j) W4 F' g1 X& @2 f
                {
                        end--;
( Y0 T0 N' e0 K
                }
  ?5 |( s5 @5 U! ~; K' A) \0 }
                while (begin 
: x0 X- Q* ?2 I# F
                        begin++;
3 x9 {$ n; h; {% V* B; |
                }
5 K- C: v! I" ^+ ^+ R6 d6 D' `' d
                Swap(&a[begin], &a[end]);
        }
9 X! n& ~+ \6 D! a9 z1 b# ~
        Swap(&a[keyi], &a[begin]);
        return begin;
}
复制代码

4前后指针法
2 v1 _! J8 L* B1 V. y9 e! B' okeyi记录begin,设prev = left, cur = left + 1让cur往后面找比key小的值找到了就给prev++然后给交换prev和cur的值一直重复直到cur>=n,prev的位置就应该放key下面是一个例子的过程
0 k  I4 V( N) m$ ~# D( Q

- i/ C9 h+ [9 c- t
4 @! r7 _2 g8 a: G! C! s" e5总代码及解析

//三数取中
int GetMidIndex(int* a, int left, int right)
) r1 c4 Q" Y) J" h& Q
{
% W9 P4 u  p+ \/ I& i5 ?
        int mid = (left + right) >> 1;
        if (a[left] 
                if (a[mid] 
                        return mid;
$ z8 C! X* ~" `1 D
                }
                else if (a[left] > a[right])
                {
                        return left;
                }
                else
1 X/ l' \, _. f6 S+ U* r
                {
3 A9 m4 B: Y6 R2 ~# ^1 b
                        return right;
" {4 w3 d4 W% W' j
                }
+ m5 }) ?/ G  q! z0 H2 z4 X
        }
* A0 e; N/ D( @8 q& a- G/ R3 F/ R
        else//a[left] > a[mid]
4 j% i3 D' `! t
        {
5 d2 N1 K5 C9 O5 H$ _' {
                if (a[mid] > a[right])
                {
                        return mid;
1 |4 |) ]# V5 ?  g( x# l0 e& K
                }
                else if (a[left] 
                        return left;
4 f5 W3 H6 S; a) }$ w' J  a2 ^
                }
3 V2 |4 U( H* K& \
                else
                {
                        return right;
4 V2 f! Y; d! R! s- ~- ^
                }
; y. a2 b, [: N3 L
        }
}
//挖坑法
int PartSort1(int* a, int left, int right)
4 s" K6 Y/ T  |% m5 d
{
        int begin = left, end = right;
        int mid = GetMidIndex(a, left, right);//三数取中
        Swap(&a[mid], &a[begin]);
5 A$ z9 p9 [# B. }9 O
        int key = a[begin];
; ^( P) V8 D" L& W( i6 ^
        int pivot = begin;
" X+ i% k: \* r# l
        while (begin 
% {9 q, L8 m; K2 W0 \
                while (begin = key)
  t& L  s# p" @$ \4 s* W
                {
                        end--;
8 o9 M) J* r! z4 k
                }
                a[pivot] = a[end];
                pivot = end;
+ G4 F! w; c$ J! ]: g" t8 u, r
                while (begin 
$ P' D$ h) n/ z: `+ X
                        begin++;
6 A. d: P3 v- h  u
                }
                a[pivot] = a[begin];
                pivot = begin;
        }
        a[begin] = key;
6 A. f. c. X6 }+ Z2 M2 ]
        return pivot;
' c1 h- Y8 z, S2 ^& U  @
}
//左右指针法
: a8 Z' j9 p; r4 ~' b2 J
int PartSort2(int* a, int left, int right)
, e; I1 a0 q% U7 T, C+ }( a7 \
{
        int mid = GetMidIndex(a, left, right);
        Swap(&a[left], &a[mid]);
. C9 Y- s. a' F$ ]6 X
        int begin = left, end = right;
, _7 r4 m9 d3 ~3 D9 b/ ?
        int keyi = begin;
8 f- w4 O. ^5 A2 b
        while (begin 
% n/ [- m+ R$ w% t0 z7 H1 ^- O
                while (begin = a[keyi])
                {
+ U4 p) `, P# z6 ]- M3 a
                        end--;
/ T. z( \4 a- y4 `1 }5 {
                }
( M7 v5 U, S/ V* u* Z% p8 J) Y
                while (begin 
                        begin++;
                }
                Swap(&a[begin], &a[end]);
        }
1 u, M% [+ t* }8 ^
        Swap(&a[keyi], &a[begin]);
        return begin;
( W( S& X  [/ X$ q. ?6 H" N/ [1 s
}
0 O9 g# F2 _  w4 y' g" n
//前后指针法
/ L7 M/ y* v1 g# R( H% n3 T
int PartSort3(int* a, int left, int right)
{
        int mid = GetMidIndex(a, left, right);
2 h3 b' e* a) b9 N! p# ?: L
        Swap(&a[left], &a[mid]);
6 ^9 `5 @) Y% b% S) ?
        int prev = left, cur = left + 1;
' Q) z0 n( u8 D8 @
        int keyi = left;
        while (cur 
                while (a[cur] 
6 v7 t- I* V- c$ {& X0 b
                        Swap(&a[prev], &a[cur]);
                }
  P, \0 O% M, K( C& ^
                ++cur;
- c. w* X1 \1 L4 N& w" F. G
        }
# K8 b8 a' C" V5 ^& q
        Swap(&a[prev], &a[keyi]);
2 F0 _0 g( H4 _  g  \
        return prev;
}
5 f& y9 h1 }# U' Q) @& [2 r2 G
void QuickSort(int* a, int left, int right)
, p5 l* N3 o. f& w
{
( P* o, `2 c, m: |+ e
        if (left >= right)
/ Q+ z3 ?6 B6 e3 d+ d
        {
/ `/ A  _5 `* H
                return;
        }
        int keyindex = PartSort3(a, left, right);//可以调用3种方法的任意一种
& `5 v1 q) M1 Q% w* f
        if (keyindex - 1 - left > 10)
" z8 W5 q; K4 c( U! s
        {
                QuickSort(a, left, keyindex - 1);
        }
: u8 w& E+ @9 k
        else
& p8 o0 q0 Y7 Z1 E& F
        {
                InsertSort(a + left, keyindex - 1 - left + 1);
( z0 ]9 E* M3 w2 v1 ]
        }
        if (right - (keyindex + 1) > 10)
        {
                QuickSort(a, keyindex + 1, right);
1 n5 H6 X3 {) j/ o7 D! w
        }
        else
+ I, h8 W4 G6 A; h& Q
        {
                InsertSort(a + keyindex + 1, right - (keyindex + 1) + 1);
        }
# t  h2 E, L6 z0 I, v8 F8 T
}
复制代码

4 q! @& N2 E2 W- q( F2 o# t2 P6注意事项及改进
* V1 P  l- b  o+ H4 G看到这里有人可能有两个疑问
1.三数取中是什么为什么要用三数取中
0 _1 }0 x+ U% s. |' n 2.快排主代码中为什么有插入排序

* |$ w  ]5 U& @) H2 w

>1.三数取中是将头和尾还有中间值这3个数中取一个·不大不小的值来当key可以有效地防止出现数据有序升序和降序的最坏的情况
>因为一旦有序每一次都相当于遍历了效率很低
>2.这快排主要是依靠递归实现的一旦区间分的很小后递归深度会很深所以被分成较小的区间时数据比较有序这时用插入排序效率更好
复制代码

+ k; A! @+ d* I1 X1 c, ^7算法总结
# J4 `. ^  h2 ~5 t5 q, H
[ol]

快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序

时间复杂度O(N*logN)

空间复杂度O(logN)

稳定性不稳定[/ol]
. n8 D, |' [( m/ w  `% e/ P
% y. H, Z8 |" Q: j三、归并排序
7 d6 @' k+ _+ x) ^7 g0 U/ R1.归并排序
" o# D0 D0 d: |! n+ ~5 f, f1算法思想

) p! O2 ?+ ?5 b: E$ ?! F/ C 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
+ {( w3 N0 }! N6 g6 Y8 a

/ Y) J9 I4 l- q* l1 v3 T$ {2算法讲解
两图解决当们将一组数据分为两半用begin1和begin2分别指向两边的数据的首元素依次比较将小的放到另外的一个数组在任意一个数组被拿完后将另外一个数组全部复制过去如果这个数组两边是有序的我们就完成了可惜两边不是有序的那我们就继续分直到分成只有一个一个数据他始终有序然后将两个一个的数组合在一起归并这两个数据就有序了然后这两个和另外的合并直到完全合并就行了
, C- R1 K" ?0 e, v# x+ z9 j1 H7 z% D* w
* K2 f. B1 A" s8 g
. I' ]" E& o7 s
# k- b9 x5 Z2 p3 {" z2 W2 _* o3 s
9 m0 q  ]/ U7 b  Z9 S& `- Z3 n) O
(3)代码及解析

void _MergeSort(int* a, int left, int right, int* temp)
* l+ W% b/ U& {% [( c, |* N
{
( }# x7 e9 h0 f
        if (left >= right)
        {
) B  t8 C2 c" g  ~
                return;
        }
& e$ O; j5 U" [# E6 L/ T1 U: D
        int mid = (left + right) >> 1;
' _! D% T& K% J; Y) C8 ]
        _MergeSort(a, left, mid, temp);
        _MergeSort(a, mid + 1, right, temp);
" k; T- U$ s- e' T( S! _. T; O
        //这里用二叉树的知识理解左右节点就是一层当我我们解决掉一层后我们就需要对这个代码进行归并
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = left;
/ P. i) V  [) d& P7 s
        while (begin1 
; {. ]& X& b, ]+ C( G; O" h3 K
                if (a[begin1] 
  f' Y( S) W3 J
                        temp[index++] = a[begin1++];
                }
                else
5 \* i, J% |/ U
                {
* j) P% A4 e0 T: O. U! M
                        temp[index++] = a[begin2++];
& ]/ v4 A+ d4 w$ M! B8 z( t) z1 r6 o
                }
* Z0 ?9 n4 k- O
        }
        while (begin1 
+ g& C6 p$ I9 E" L9 a. e8 p$ F
                temp[index++] = a[begin1++];
7 i* q; ]7 s% o8 `0 q+ f8 J  G
        }
        while (begin2 
5 }* [& A5 r% h' w( i" s" C1 f( o) G
                temp[index++] = a[begin2++];
        }
        for (int i = left; i 
                a[i] = temp[i];
7 P, |7 g; r* |7 `1 }# l3 q
        }
}
% t; ^9 M7 z1 S! i+ p; j. \
void MergeSort(int* a, int m)
{
        int* temp = (int*)malloc(sizeof(int) * m);
        _MergeSort(a, 0, m - 1, temp);
  o+ h0 y2 u) p: q$ r" n0 U
        free(temp);
# Z+ L( t6 s: X0 B+ e1 K
}
8 u9 {) `; ~; G3 N) O( w
复制代码

, z$ y3 ]" W9 V$ a4算法总结

[ol]

归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问
% D! _6 h1 [2 J4 @+ N1 ^7 \ 题。

时间复杂度O(N*logN)

空间复杂度O(N)

稳定性稳定[/ol]

. o/ a- {$ R& ?1 g4 \总结

% L" @! B6 r- e+ ^ 好了这篇文章总算爆肝完了哭希望对你有帮助有错误请指正谢谢
               
               
& }+ k  `; a% b/ W1 y               
本文来源csdn，由Java吧转载发布，观点不代表Java吧的立场，转载请标明来源出处：https://www.java8.com