数据结构一排序算法

排序算法总结

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。假设长度为n的数组arr，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最左端的元素即为该数组中所有元素的最小值。接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。

冒泡排序的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个；
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现如下：

/*冒泡排序*/
class Bubbling_Sort
{
	/*时间复杂度O(n*n),空间复杂度O(1)，有相对稳定性*/
public:
	void bub_sort(vector<int>& arr)
	{
		for (int i = 0; i < arr.size(); i++)
		{
			for (int j = arr.size() - 1; j > i; j--)
			{
				if (arr[j-1] > arr[j])
				{
					arr[j] = arr[j] ^ arr[j - 1];
					arr[j-1] = arr[j] ^ arr[j - 1];
					arr[j] = arr[j] ^ arr[j - 1];
				}
			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，则将最小值min1和arr[0]交换，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。算法的时间复杂度为O(n^2)。

选择排序算法的原理如下：

1. ​首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 ​
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 ​
3. 重复第二步，直到所有元素均排序完毕

。
代码如下：

class Choose_Sort
{
	/*时间复杂度O(n*n),空间复杂度O(1),没有相对稳定性*/
public:
	void c_sort(vector<int>& arr)
	{
		for (int i = 0; i < arr.size(); i++)
		{
			for (int j = i+1; j < arr.size(); j++)
			{
				if (arr[i] > arr[j])
				{
					arr[i] = arr[i] ^ arr[j];
					arr[j] = arr[i] ^ arr[j];
					arr[i] = arr[i] ^ arr[j];
				}
			}
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

插入排序

​ 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。该算法的时间复杂度为O(n^2)。

插入排序算法的原理如下：

1. ​从第一个元素开始，该元素可以认为已经被排序；
2. ​取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. ​重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

代码如下：

class Insert_Sort
{
/*插入排序时间复杂度是O(n*n),空间复杂度是O(1)，有相对稳定性*/
public:
	void In_sort(vector<int>& arr)
	{
		for (int i = 0; i < arr.size(); i++)
		{
			for (int j = i; j>0; j--)
			{
				if (arr[j-1] < arr[j])
					break;
				sort(arr, j - 1, j);
			}
		}
	}

	void sort(vector<int>& arr, int i, int j)
	{
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。代价是需要额外的内存空间。若将两个有序表合并成一个有序表，称为2-路归并。 该算法时间复杂度为O(nlogn)。

归并排序算法的原理如下：

1. ​把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序； ​
3. 将两个排序好的子序列合并成一个最终的排序序列。

代码如下：

class Merge_sort{
/*归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)，有相对稳定性*/
public:
    void Me_sort(vector<int> &arr,int Left,int Right){
        if(Left >= Right)
            return;

        int mid = Left + ((Right-Left) >> 1);
        Me_sort(arr,mid+1,Right);
        Me_sort(arr,Left,mid);
        Merge(arr,mid,Left,Right);
    }

    void Merge(vector<int> &arr,int mid,int Left,int Right){
        int *buf = new int[Right - Left + 1];
        int bufsize = 0;
        int i=Left;
        int j=mid+1;

        while(i<=mid && j<=Right){
            if(bufsize >= Right - Left + 1)
                break;
            buf[bufsize++] = arr[i] <= arr[j] ? arr[i++]:arr[j++];
        }

        while(i<=mid){
            if(bufsize >= Right - Left + 1)
                break;
            buf[bufsize++] = arr[i++];
        }

        while(j<=Right){
            if(bufsize >= Right - Left + 1)
                break;
            buf[bufsize++] = arr[j++];
        }

        for(int k=0;k<bufsize;k++){
            if(Left + k > Right)
                break;
            arr[Left+k] = buf[k];
        }

        delete[] buf;
    }
};
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

快速排序

快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。一趟快速排序的具体过程可描述为：从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值，然后将记录中关键字比它小的记录都安置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。它是处理大数据最快的排序算法之一了。该算法时间复杂度为O(n log n)。

快速排序算法的原理如下：

1. ​从数列中挑出一个元素，称为 “基准”（pivot）;
2. ​重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. ​递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码如下：

class Quick_Sort
{
	/*时间复杂度为O(nlogn),空间复杂度为O(logn)，没有相对稳定性*/
	int* p = new int[2];
public:
	void quick_sort(vector<int>& arr, int Left, int Right)
	{
		if (Left >= Right)
			return;

		swap(arr, Left + (rand() * (Right - Left) / RAND_MAX), Right);
		int* p = partition(arr, Left, Right);

		quick_sort(arr, Left, p[0]-1); // <区
		quick_sort(arr, p[1]+1, Right);// >区
	}

	void swap(vector<int>& arr ,int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	int* partition(vector<int>& arr, int Left, int Right)
	{
		int L = Left-1;
		int R = Right;
		int P = Left;

		while (P < R)
		{
			if (arr[P] > arr[Right])
				swap(arr, P, --R);
			else if (arr[P] < arr[Right])
			{
				swap(arr, ++L, P++);
			}
			else
				P++;
		}

		swap(arr, R, Right);
		p[0] = L+1;
		p[1] = R;
		return p;
	}

	~Quick_Sort() {
		delete[] p;
	}
};
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

堆排序

​堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。该算法时间复杂度为O(nlogn)。

代码实现如下：

class Heap_Sort
{
	/*堆排序的时间复杂度为O(nlogn),空间复杂度为O(1)，没有相对稳定性*/
public:
	void heap(vector<int>& arr)
	{
		if (arr.empty() || arr.size() < 2)
			return ;

		for (int i = 0; i < arr.size(); i++)
		{
			heap_insert(arr, i);
		}
		int heapsize = arr.size();

		swap(arr, 0, --heapsize);

		while (heapsize>0)
		{
			heapify(arr, 0, heapsize);
			swap(arr, 0, --heapsize);
		}
	}

	void heap_insert(vector<int>& arr, int temp)
	{
		while (temp > 0 && arr[(temp - 1) / 2] < arr[temp])
		{
			swap(arr, (temp - 1) / 2, temp);
			temp = (temp - 1) / 2;
		}
	}
	
	void swap(vector<int>& arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	void heapify(vector<int>& arr, int index, int heapSize)
	{
		int left = (index * 2) + 1;

		while (left < heapSize)
		{
			/*这里很细节要注意当left+1大于heapsize时是否要取left*/
			int leagues = left + 1 < heapSize && arr[left+1] > arr[left] ? left+1 : left;
			leagues = arr[index] < arr[leagues] ? leagues : index;

			if (index == leagues)
				break;

			swap(arr, index, leagues);
			index = leagues;
			left = (index * 2) + 1;
		}
	}
};
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

总结：

复杂度

为O(n^2)的有：冒泡排序、选择排序、插入排序、希尔排序；
为O(nlogn)的有：快速排序、归并排序、堆排序；

稳定性

具有相对稳定性的是：冒泡排序、插入排序、归并排序；
没有相对稳定性的是：选择排序、快速排序、堆排序；