排序（上）

Posted on   |   In   |  

排序简介

一.简单排序

  • 1.冒泡排序
    • 伪代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      void BubbleSort(ElemenType A[], int N)
      {
      	for(int i = N; i >= 0; --i)
      	{
      		flag = 0;	//标志位
      		for(int j = 0; j < P; ++j)
      		{
      			if(A[j] > A[j + 1])
      			{
      				Swap(A[j], A[j + 1]);	//注意这里交换的是相邻元素，跟插入排序的区别
      				flag = 1;		//说明存在交换
      			}
      		}
      		if(flag)
      		{
      			break;	//全程无交换，说明已经排行序，无需继续进行下去
      		}
      	}
      }
* 时间复杂度
最好情况：O(N)----本来就是排序好的数据，一遍循环无交换，break
最坏情况：O(N^2)---完全倒序

* 冒泡排序是**稳定**的
  • 2.插入排序
    • 伪代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void InsertionSort(ElemenType A[], int N)
      {
      	for(int i = 1; i < N; ++i)
      	{
      		temp = A[i];	//下一个元素
      		int j = i;
      		for(; j > 0 && a[j - 1] > temp; --j)
      		{
      			A[j] = A[j - 1];//移动元素，留出空位
      		}
      		A[j] = temp;	//插入到该空位
      	}
      }
* 时间复杂度
最好情况：O(N)
最坏情况：O(N^2) -- 完全倒序
* 插入排序是**稳定**的
  • 3.时间复杂度下界
    • 对于下标i < j，如果A[i] > A[j]，则称(i,j)是一对逆序对(inversion)
      交换两个相邻元素可以消去一个逆序对
      插入排序 时间复杂度 T(N, I) = O(N + I)//I是交换次数
    • 定理：任意N个不同元素组成的序列平均具有N(N-1)/2;
    • 定理：任何仅以交换相邻元素来排序的算法，其平均时间复杂度为Ω(N^2)
      所以要想提高算法效率，必须
      • 每次消去不止一个逆序对
      • 每次交换相隔较远的2个元素

二.希尔排序

  • 思想
    定义增量序列Dm > Dm-1 ··· D1 = 1
    对Dk进行“Dk-间隔”排序（K= M，M-1，···1）
    注意：“Dk-间隔”有序的序列，在执行“Dk-1间隔”排序后，仍然是“Dk-间隔”有序的，例如：先进行5间隔排序，在进行3间隔排序后，该序列仍然是5间隔有序（每隔5个元素大小有序）
    • 原始希尔排序的增量序列Dm= N/2向下取整，然后 Dk = Dk/2;
    • 伪代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void ShellSort(ElemenType A[], int N)
      {
      for(D = N/2; D>0; D/=2)		//希尔增量排序
      {
      	for(P = D; P < N; ++P)	//插入排序
      	{
      		temp = A[P];
      		for(i = P; i >= D && A[i - D] > temp; i -= D)
      		{
      			A[i] = A[i - D];
      		}
      		A[i] = temp;
      	}
      }
      }
  • 时间复杂度： 最坏情况：Θ(N^2)–对于前几次希尔增量序列，每一次比较实际上内部的插入排序并未交换位置，只在最后一次1间隔的时候，做交换，这就导致了前几次的循环浪费了，还不如直接做插入排序
    可以通过使增量序列互质来避免这种情况，如Hibbard增量序列Dk = 2^K - 1,增量元素相邻互质，最坏情况是Θ(N^(3/2));Sedgewick增量序列{1,5,19,41,109,···} – 94^i-92^i+1或4^i-3*2^i+1
  • 希尔排序是不稳定 的

三.堆排序

  • 选择排序
    • 伪代码
      1
      2
      3
      4
      5
      6
      7
      8
      void SelectionSort(ElemenType A[], int N)
      {
      	for(int i = 0; i < N; ++i)
      	{
      		MinPosition = ScanForMin(A, i, N-1);	//选出最小的，相当于一个for循环扫描
      		Swap(A[i], A[MinPosition]);
      	}
      }
* 时间复杂度 Θ(N^2)
  选择排序的瓶颈在ScanForMin，如何快速找到最小元素，就能提高算法效率
  • 堆排序（选择排序的改进）
    • 算法1
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      void HeapSort(ElemenType A[], int N)
      {
      	BuildHeap(A);		//O(N),有O(N)的算法来创建最小堆
      	for(int i = 0; i < N; ++i)		//O(NlogN),因为DeleteMinHeap的操作是O(logN)的
      	{
      		temp[i] = DeleteMinHeap(A);
      	}
      	for(int i = 0; i < N; ++i)		//O(N)
      	{
      		A[i] = temp[i];
      	}
      }
*时间复杂度 O(N * logN)
缺点是：需要开额外的O(N)空间来存储temp数组，且赋值到A也耗时O(N)
* 算法2

1
2
3
4
5
6
7
8
9
10
11
12
void HeapSort(ElemenType A[], int N)
{
	for(i = N/2; i >= 0; --i)	//build Heap
	{
		PercDown(A,i,N);
	}
	for(i = N - 1; i > 0; --i)
	{
		Swap(A[0], A[i]);	//delete Max elements
		PercDown(A, 0, i);
	}
}


* 定理： 堆排序处理N个不同元素的随机排列的平均次数是2NlogN-O(NloglogN)
* 虽然堆排序给出的最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序

四.归并排序

  • 核心算法：有序子列的归并

    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
    //L= 左边起始位置，R=右边起始位置， rightEnd = 右边终点位置
    void Merge(ElemenType A[], ElemenType temp[], int L, int R, int rightEnd)
    {
    	leftEnd = R - 1;	//左边终点位置，这里假设的是两个子序列是紧挨着的
    	int elementsNum = RightEnd - L + 1;		//存放结果的数组的长度
    	int tmp = L;						//存放结果数组的初始位置
    	while(L <= leftEnd && R <= RightEnd)
    	{
    		if(A[L] <= A[R])
    		{
    			temp[tmp++] = A[L++];
    		}
    		else
    		{
    			temp[tmp++] = A[R++];
    		}

    	}
    	while(L <= leftEnd)			//复制左边剩下的
    	{
    		temp[tmp++] = A[L++];
    	}
    	while(R <= rightEnd)		//复制右边剩下的，(左边和右边最多只会有一个剩下的，或者一个都不剩)
    	{
    		temp[tmp++] = A[R++];
    	}
    	for(int i = 0; i < elementsNum; ++i, --rightEnd)
    	{
    		A[rightEnd] = temp[rightEnd];
    	}
    }

  • 递归算法
    分而治之(自顶向下)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void MSort(ElemenType A[], ElemenType TempA[], int L, int rightEnd)
    {
    	int center;
    	if(L < rightEnd)
    	{
    		center = (L + rightEnd) / 2;
    		MSort(A, TempA, L, center);
    		MSort(A, TempA, center + 1, rightEnd);
    		Merge(A, TempA, L, center + 1, rightEnd);
    	}
    }
T(N) = T(N/2) + T(N/2) + O(N) --> T(N) = O(NlogN)

统一函数接口
void MergeSort(ElemenType A[], int N)
{
    ElemenType *TempA = new int[N];
    if(TempA != NULL)
    {
        MSort(A, TempA, 0, N-1);
        delete []TempA;
    }
    else
    {
        cout << "空间不足" << endl;
    }
}
  • 非递归算法（自底向上） 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void Merge_pass(ElemenType A[], ElemenType TempA[], int N, int length)
    {
    	for(int i = 0; i <= N - 2*length; i += 2*length)
    	{
    		Merge1(A, TempA, i, i + length, i + 2 * length - 1);
    	}
    	if(i + length < N)
    	{
    		Merge1(A, TempA, i, i + length, N - 1);		//这里的merge1跟上面的merge有个小区别就是元素归一在TempA里，也就是说上面的merge函数把最后一个for循环去掉就ok了
    	}
    	else
    	{
    		for(j = i; i < N; ++j)
    		{
    			TempA[j] = A[j];
    		}
    	}
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void MergeSort(ElemenType A[], int N)
{
	ElemenType *TempA = new int[N];
	if(TempA != NULL)
	{
		while(length < N)
		{
			Merge_pass(A, TempA, N, length);
			length *= 2;
			Merge_pass(A, TempA, N, length);	//这里第二次做Merge不用担心length超过N，即使超过N，在Merge函数里只是做了赋值，执行的是else里的for循环语句
			length *= 2;
		}
		delete []TempA;
	}
	else
	{
		cout << "no enough memory" << endl;
	}
}