数据结构一排序算法

排序算法总结

冒泡排序

冒泡排序（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];}}}}
};

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 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];}}}}
};

插入排序

​ 插入排序（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];}
};

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（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;}
};

快速排序

快速排序通常明显比其他 Ο(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++);}elseP++;}swap(arr, R, Right);p[0] = L+1;p[1] = R;return p;}~Quick_Sort() {delete[] p;}
};

堆排序

​堆排序（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;}}
};

总结：

复杂度

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

稳定性

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