Sort_Algorithms

发表于 | 更新于: | 分类于 | 热度: ℃
字数统计: 4,283 | 阅读时长 ≈ 19

前言

　　查找和排序是算法的入门知识，因为实现代码较短，应用较常见．面试中经常会问到排序算法及相关的问题．一般在面试中最常考的是快速排序和归并排序，并且要求现场写出这两种排序的代码．对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。接下来我们就分析一下常见的排序算法及其使用场景。

冒泡排序

　　冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此二得名．举个例子：对5,3,8,6,4这个无序序列进行冒泡排序．首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstdlib>
using namespace std;
int data[1000];
void Bubble_sort(int *d, int n){
  for(int k=1; k<n; k++)
  {
    for(int i=1; i＜n; i++)
    {
      if(d[i]<d[i-1])
      {
        int temp = d[i];
        d[i] = d[i-1];
        d[i-1] = temp;
      }
    }
  }
}
int main()
{
  for(int i=0; i<1000; i++)
  {
    data[i] = rand();
  }
  Bubble_sort(data, 1000);
  for(int i=0; i<1000; i++)
  {
    printf("%d\n", data[i]);
  }
  return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Bubble_sort
{
  public static void Bubble_sort(int[] arr)
  {
    if(arr == null || arr.length = 0)
      return ; 
    for(int i=0; i<arr.length-1; i++)
    {
      for(int j=0; j<arr.length; j++)
      {
        if(arr[j]>arr[j+1])
        {
          int temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    }
  }
}

选择排序

选择排序的思想和冒泡排序有些类似，都是在一次排序后吧最小的元素放在最前面．但是过程不同，冒泡排序是通过相邻的比较和交换，选择排序是通过对整体的选择．举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，依次排序后就编程3,5,8,6,4.对剩下的序列一次进行选择和交换，最终会得到一个有序序列．选择排序可以看作是冒泡排序的优化，其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数．选择排序的时间复杂度为O(n^2)。

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#define ELEMENT_COUNT 10000;
using namespace std;
int n, k, d[ELEMENT_COUNT];
int partition(int l, int r)
{
  int x = d[r];
  int j = l-1;
  for(int i=1; i<=r; i++)
  {
    if(d[i]<=x)
    {
      j++;
      int temp = d[i];
      d[i] = d[j];
      d[j] = temp;
    }
  }
  return j+1;
}
int select(int k)
{
  int l = 0, r = n-1;
  while(l<r)
  {
    int par = partition(l, r);
    if(par < k)
    {
      l = par;
    }
    else if(par>k)
    {
      r = par-2;
    }
    else
    {
      return d[par-1];
    }
  }
  return d[l];
}
inr main()
{
  scanf("%d%d", &n, &k);
  for(int i=0; i<n; i++)
  {
    scanf("%d", &d[i]);
  }
  int ktg = select(k);
  printf("%d", kth);
  return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Select_sort
{
  public static void Select_sort(int[], arr)
  {
    if(arr == null || arr.length = 0)
      return ; 
    int minIndex = 0;
    for(int i=0; i<arr.length; i++)  //只需要比较n-1次
    {
      minIndex = i;
      for(int j=i+1; j<arr.length; j++)  
      {                          //从i+1开始比较，因为minIndex默认为i了，i就没必要比了。
        if(arr[j]<arr[minIndex])
        {
          minIndex = j;
        }
      }
      if(minIndex != i)　　　//如果minIndex不为i，说明找到了更小的值，交换之。
      {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
    }
  }
}

插入排序

插入排序表示通过交换位置而是通过比较找到合适的位置插入元素来达到怕徐的目的．举个例子：对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一位数的位置是正确的，然后3要插到5前面，把5后移一位，变成3,5,8,6,4.然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#define ELEMENT_COUNT 10000;
using namespace std;
int n, d[ELEMENT_COUNT];
void Insertion_sort()
{
  for(int i=1; i<n; i++)
  {
    for(int j=i-1; j>=0; j--)
    {
      if(d[j]>d[j+1])
      {
        int temp = d[j];
        d[j] = d[j+1];
        d[j+1] = temp;
      }
      else
      {
        break;
      }
    }
  }
}
int main()
{
  scanf("%d", &n);
  for(int i=0; i<n; i++)
  {
    scanf("%d", &d[i]);
  }
  Insertion_sort();
  for(int i0; i<n; i++)
  {
    printf("%d\n", d[i])
  }
  return 0 ;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Insertion_sort
{
  public static void Insertion_sort(int[] arr) 
  {                              //假设第一个数位置时正确的；要往后移，必须要假设第一个。
    if(arr == null || arr.length == 0)
      return ; 
    for(int i=1; i<arr.lengt; i++)
    {
      int j = i;
      int target = arr[i];   //待插入的
      //后移
      while(j>0 && target < arr[j-1])
      {
        arr[j] = arr[j-1];
        j--;
      }
      
      //插入
      arr[j] = target;
    }
  }
}

快速排序

在实际应用中，快速排序是表现最好的排序算法．快速排序思想来自于冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换大数和小数，这样一来不仅吧小数冒泡到上面同时也把大数沉到下面．

举个例子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。

  • 5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
  • 5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。
  • 5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
  • 4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstdlib>
#define MAX_ELEMENT_COUNT 1000000
using namespace std;
int d[MAX_ELEMENT_COUNT];
void Qucik_sort(int l, int r)
{
  if(l<r)
  {
    int x = d[r];
    int j= l-1;
    
    for(int i=1; i<=r; i++)
    {
      if(d[i]<=x)
      {
        j++;
        int temp = d[i];
        d[i] = d[j];
        d[j] = temp;
      }
    }
    Qucik_sort(l, j-1);
    Qucik_sort(j+1, r)
  }
}
int main()
{
	for (int i = 0; i < MAX_ELEMENT_COUNT; i++)
	{
		d[i] = rand();
	}
	
	Qucik_sort(0, MAX_ELEMENT_COUNT - 1);
	
	for (int i = 0; i < MAX_ELEMENT_COUNT; i++)
	{
		printf("%d\n", d[i]);
	}
	
	return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Quick_sort
{
  	/**
	 * 从left到right排序数组array
	 * @param arr
	 * @param left
	 * @param right
	 */
  public static int partition(int[] arr, int left, int right)
  {
    int pivotkey = arr[left];
    
    while(left<right)
    {
      while(left<right && arr[right]>=pivotkey)
        right--;
      arr[left] = arr[right]; //把小的移动到左边
      while(left<right && arr[left]<=pivotkey)
        left++;
      arr[right] = arr[left]; //把大的移动到右边
    }
    arr[left] = pivotkey; //最后把pivot赋值到中间
    return left;
  }
  
  /**
     * 递归划分子序列
     * @param arr
     * @param left
     * @param right
     */
  public static void quick_sort(int[] arr, int left, int right)
  {
    if(left >= right)
      return ;
    int pivotPos = partition(arr, left, right);
    quick_sort(arr, left, pivotPos-1);
    quick_sort(arr, pivotPos+1, right);
  }
  public static void sort(int[] arr)
  {
    if(arr == null || arr.length == 0)
      return ;
    quick_sort(arr, 0, arr.length-1);
  }
  　　
}

堆排序

堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。

　　首先，实现堆排序需要解决两个问题：

  　　1. 如何由一个无序序列键成一个堆？

  　　2. 如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？

　　第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第一个非叶元素开始挨个调整成一个堆。

　　第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。

　　从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个非终端节点是n/2取底个元素，由此筛选即可。举个栗子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和调整的过程如下：

堆

堆去

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<cstdlib>
#define MAX_HEAP_SIZE 10000;
using namespace std;
int n, H[MAX_HEAP_SIZE], heapsize;
void min_heapify(int i)
{
  int smallest = i;
  int lch = i <<1;
  int rch = lch+1;
  
  if(lch <= heapsize && H[smallest]>H[lch])
  {
    smallest = lch;
  }
   if(rch <= heapsize && H[smallest]>H[rch])
  {
    smallest = rch;
  }
  if(smallest != i )
  {
    int temp = H[smallest];
    H[smallest] = H[i];
    H[i] = temp;
    min_heapify(smallest);
  }
}
void build_heap()
{
  for(int i = heapsize >>1; i>=1; i--)
  {
    min_heapify(i)
  }
}
int extract_min()
{
  int res = H[1];
  H[1] = H[heapsize--];
  min_heapify(1);
  return res;
}
int main()
{
	scanf("%d", &n);
	heapsize = n;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &H[i]);
	}
	build_heap();
	while (heapsize > 0)
	{
		printf("%d\n", extract_min());
	}
	
	return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class HeapSort {
    
    /**
     * 堆筛选，除了start之外，start~end均满足大顶堆的定义。
     * 调整之后start~end称为一个大顶堆。
     * @param arr 待调整数组
     * @param start 起始指针
     * @param end 结束指针
     */
    public static void heapAdjust(int[] arr, int start, int end) {
        int temp = arr[start];
        
        for(int i=2*start+1; i<=end; i*=2) {
            //左右孩子的节点分别为2*i+1,2*i+2
            
            //选择出左右孩子较小的下标
            if(i < end && arr[i] < arr[i+1]) {
                i ++; 
            }
            if(temp >= arr[i]) {
                break; //已经为大顶堆，=保持稳定性。
            }
            arr[start] = arr[i]; //将子节点上移
            start = i; //下一轮筛选
        }
        
        arr[start] = temp; //插入正确的位置
    }
    
    
    public static void heapSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        
        //建立大顶堆
        for(int i=arr.length/2; i>=0; i--) {
            heapAdjust(arr, i, arr.length-1);
        }
        
        for(int i=arr.length-1; i>=0; i--) {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i-1);
        }
        
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

希尔排序

希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

举个例子：

希尔

从上述排序过程可见，希尔排序的特点是，子序列的构成不是简单的逐段分割，而是将某个相隔某个增量的记录组成一个子序列。如上面的例子，第一堂排序时的增量为5，第二趟排序的增量为3。由于前两趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地向前挪动，而是跳跃式地往前移，从而使得进行最后一趟排序时，整个序列已经做到基本有序，只要作记录的少量比较和移动即可。因此希尔排序的效率要比直接插入排序高。

　　希尔排序的分析是复杂的，时间复杂度是所取增量的函数，这涉及一些数学上的难题。但是在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)。

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#define ELEMENT_COUNT 100000
using namespace std;
int n, d[ELEMENT_COUNT];
void Shell_sort()
{
  for(int gc = n>>1; gc>=1; gc>>=1)
  {
    for(int s = 0; s<gc; s++)
    {
      for(int j = i-gc; j>=0 && d[j]>d[j+gc]; j-= gc)
      {
        int temp = d[j];
        d[j] = d[j+gc];
        d[j+gc] = temp;
      }
    }
  }
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &d[i]);
	}
	Shell_sort();
	for (int i = 0; i < n; i++)
	{
		printf("%d ", d[i]);
	}
	return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Shell_sort
{
  public static void shellInsert(int[] arr, int d)
  {
    for(int i=d; i<arr.length; i++)
    {
      int j = i-d;
      int temp = arr[i];   //记录要插入的数据
      while(j>=0 && arr[j]>temp)  //从后向前，找到比其小的数的位置 
      {
        arr[j+d] = arr[j];  //向后挪动 
        j -= d;
      }
      if(j != i-d)  //存在比其小的数
        arr[j+d] = temp;
    }
  }
  public static void shell_sort(int[] arr)
  {
    if(arr == null || arr.length == 0)
            return ;
    int d = arr.length / 2;
    while(d>=1)
    {
      shell_sort(arr, d);
      d /= 2;
    }
  }
}

归并排序

归并排序是另外一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易．其基本思想是，先递归划分子问题，然后合并结果．把待排序列看成由两个有序的子序列，然后合并两个子序列．然后再把子序列看成由两个有序序列．．．两两合并，四四合并．最终形成有序序列．空间复杂度为O(n)，时间复杂度为O(nlogn)。

举个例子：

归并排序

C++实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstdlib>
#define INF 2000000000
#define MAX_ELEMENT_COUNT 100000
using namespace std;
int d[MAX_ELEMENT_COUNT];
void merge(int l, int m, int r)
{
	static int al[MAX_ELEMENT_COUNT], ar[MAX_ELEMENT_COUNT];
	int il, ir;
	
	// Copy the data to the temporary array al & ar.
	for (il = l; il <= m; il++)
	{
		al[il] = d[il];
	}
	al[m + 1] = INF;
	for (ir = m + 1; ir <= r; ir++)
	{
		ar[ir] = d[ir];
	}
	ar[r + 1] = INF;
	
	// Merge al & ar into array d.
	il = l;
	ir = m + 1;
	for (int i = l; i <= r; i++)
	{
		if (al[il] < ar[ir])
		{
			d[i] = al[il++];
		}
		else
		{
			d[i] = ar[ir++];
		}
	}
}
void merge_sort(int l, int r)
{
	if (l < r)
	{
		int mid = (l + r) >> 1;
		merge_sort(l, mid);
		merge_sort(mid + 1, r);
		merge(l, mid, r);
	}
}
int main()
{
	for (int i = 0; i < MAX_ELEMENT_COUNT; i++)
	{
		d[i] = rand();
	}
	
	merge_sort(0, MAX_ELEMENT_COUNT - 1);
	
	for (int i = 0; i < MAX_ELEMENT_COUNT; i++)
	{
		printf("%d\n", d[i]);
	}
	
	return 0;
}

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Merge_sort
{
  public static void merge_sort(int[] arr)
  {
    mSort(arr, 0, arr.length-1);
  }
    /**
     * 递归分治
     * @param arr 待排数组
     * @param left 左指针
     * @param right 右指针
     */
  public static void mSort(int[] arr, int left, int right)
  {
    if(left>=right)
      return ;
    int mid = (left+right)/2;
    
    mSort(arr, left, mid);  //递归排序左边
    mSort(arr, mid+1, right); //递归排序右边
    merge(arr, left, mid, right);  //合并
  }
    /**
     * 合并两个有序数组
     * @param arr 待合并数组
     * @param left 左指针
     * @param mid 中间指针
     * @param right 右指针
     */
  public static void merge(int[] arr, int left, int mid, int right)
  {
    int [] temp = new int[right-left+1]; //中间数组
    
    int i = left;
    int j = mid+1;
    int k = 0;
    while(i<=mid && j<=right)
    {
      if(arr[i]<=arr[i])
      {
        temp[k++] = arr[i++];
      }
      else
      {
        temp[k++] = arr[j++];
      }
    }
    while(i<=mid)
    {
      temp[k++] = arr[i++];
    }
    while(j<=right)
    {
      temp[k++] = arr[j++];
    }
    for(int p=0; p<temp.length; p++)
    {
      arr[left+p] = temp[p];
    }
  }
}

计数排序

　　如果在面试中有面试官要求你写一个O(n)复杂度的排序算法，这时候需要有一个前提条件，就是待排序的数要满足一定范围的整数，而且计数排序需要比较多的辅助空间．其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数．然后依次输出即可得到有序序列．

java实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Count_sort
{
  public static void countSort(int[] arr)
  {
    if(arr == null || arr.length == 0 )
      return ;
    int max = max(arr);
    
    int[] count  = new int[max+1];
    Arrays.fill(count, 0);
    
    for(int i=0; i<arr.length; i++)
    {
      count[arr[i]]++;
    }
    int k=0;
    for(int i=0; i<=max; i++)
    {
      for(int j=0; j<count[i]; j++)
      {
        arr[k++] = i;
      }
    }
  }
  
  public static int max(int[] arr)
  {
    int max = Integer.MIN_VALUE;
    for(int els : arr)
    {
      if(ele > max)
        max = ele;
    }
    return max;
  }
}
-------------本文结束感谢您的阅读-------------
很有帮助，打赏感谢！
分享到： QQ好友 微信 新浪微博 有道云笔记 豆瓣 收藏夹 复制网址 一键分享 更多
0%