【排序】排序

快速排序概念：交换排序

• 排序思想：分治法
  • 以一个数作为基准，将所有小于该数的元素放到左边，所有大于该数的元素放到右边
  • 也就是找到该数应该存在的 “位置”，然后将排序的数组分为该数之前和该数之后
• 时间复杂度
  • 平均时间复杂度：O(nlogn)，最坏情况下：O( n 2 n^2 n2)
  • 当数据基本有序，或者数据成单只树的结构时，排序效率很低

挖坑法：

1. 找到一个基准值key，从两边开始向中间遍历
2. 先从右边开始往左遍历，找到比key小的值，将这个值赋值给arr[left]
3. 再从左边开始往右遍历，找到比key大的值，将这个值赋值给arr[right]
4. 当left == right时，就找到了key的正确位置，此时key左边的元素都小于key，右边的元素都大于key

#include 
#include 
using namespace std;
class Sort
{
public:static int Quick1(vector<int>& arr, int left, int right){int key = arr[left];	// 基准值keywhile (left < right){while (left < right && arr[right] >= key)	// 先遍历右边找到一个较小数right--;arr[left] = arr[right];while (left < right && arr[left] < key)		// 再遍历左边找到一个较大数left++;arr[right] = arr[left];}arr[left] = key;return left;}static void QuickSort(vector<int>& arr, int left, int right){if (left >= right)return;int pos = Quick1(arr, left, right - 1);QuickSort(arr, left, pos);QuickSort(arr, pos + 1, right);}
};
int main()
{vector<int> arr = { 4,5,1,6,2,7,3,8 };Sort::QuickSort(arr, 0, arr.size());return 0;
}

双指针法：

1. 先找到一个基准值key，定义一个指针pos先处于left位置
2. 从left+1开始向后依次遍历，当遇到比key小的元素，让pos++，并交换arr[pos] 和 arr[i] 的值
3. 当遍历完数组，pos最后的位置就是key应该存在的位置，交换arr[pos] 和 arr[left]

#include 
#include 
using namespace std;
class Sort
{
public:static int Quick1(vector<int>& arr, int left, int right){// 优化：找一个中间值，防止单支树的情况int key = arr[left];int pos = left;for (int i = left + 1; i <= right; i++){if (key > arr[i]){pos++;if (pos != i)		// 这里判断 pos != i，只是减少了多余的交换情况swap(arr[i], arr[pos]);}}swap(arr[left], arr[pos]);return pos;}static void QuickSort(vector<int>& arr, int left, int right){// 优化：数据量较小时使用直接插入排序if (left >= right)return;int pos = Quick1(arr, left, right - 1);QuickSort(arr, left, pos);QuickSort(arr, pos + 1, right);}
};
int main()
{vector<int> arr = { 4,5,1,6,2,7,3,8 };Sort::QuickSort(arr, 0, arr.size());return 0;
}

非递归法

void QuickSortNor(vector<int>& arr, int left, int right) 
{stack<int> stc;stc.push(left);stc.push(right);while (!stc.empty()){int end = stc.top();stc.pop();int begin = stc.top();stc.pop();int pos = _QuickSort(arr, begin, end - 1);if (begin < pos - 1){stc.push(begin);stc.push(pos);}if (end > pos + 1){stc.push(pos + 1);stc.push(end);}}
}

优化：

• 当数据量比较少的时候：使用直接插入排序，效率高于快速排序
• 为了防止单支树(数据基本有序)的情况：每次选基准值的时候，在left、right、mid三个数中找到一个中间值作为基准
• 当递归调用层数太深，使用堆排序

// 寻找中间值
void findMid(vector<int>& arr, int left, int right)
{int mid = ((left + right) >> 1);if (arr[mid] > arr[left])swap(arr[mid], arr[left]);if (arr[mid] > arr[right])swap(arr[mid], arr[right]);if (arr[left] > arr[right])swap(arr[left], arr[right]); 
}

#include 
#include 
using namespace std;
class Sort
{
public:static void QuickSort(vector<int>& arr, int left, int right){if (left >= right)return;int pos = _QuickSort(arr, left, right - 1);QuickSort(arr, left, pos);QuickSort(arr, pos + 1, right);}static void MergeSort(vector<int>& arr, int left, int right){if (arr.empty())return;vector<int> tmp(right - left);_MergeSort(arr, left, right - 1, tmp);}static void HeapSort(vector<int>& arr, int left, int right){// 升序建大堆，从最后一个分支开始向下调整int pos = (right - 2) / 2;for (int i = pos; i >= 0; --i){_AdjustDown(arr, i, right);}while (right--){swap(arr[left], arr[right]);_AdjustDown(arr, left, right);}}
private:static void _MergeSort(vector<int>& arr, int left, int right, vector<int>& tmp){if (left >= right)return;int mid = left + (right - left) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);int begin1 = left, begin2 = mid + 1;int pos = left;while (begin1 <= mid && begin2 <= right){if (arr[begin1] <= arr[begin2])tmp[pos++] = arr[begin1++];elsetmp[pos++] = arr[begin2++];}while (begin1 <= mid)tmp[pos++] = arr[begin1++];while (begin2 <= right)tmp[pos++] = arr[begin2++];for (int i = left; i <= right; ++i)arr[i] = tmp[i];}static int _QuickSort(vector<int>& arr, int left, int right){// 三数取中int key = arr[left];// 挖坑法while (left < right){while (left < right && arr[right] >= key)--right;arr[left] = arr[right];while (left < right && arr[left] < key)++left;arr[right] = arr[left];}arr[left] = key;return left;}static void _AdjustDown(vector<int>& arr, int parent, int n){// 将元素较大的向上调整int child = parent * 2 + 1;while (child < n){// 找左右子树较大的if (child + 1 < n && arr[child] < arr[child + 1])++child;// 如果子树值较大，则交换，否则位置已经找到返回if (arr[parent] < arr[child]){swap(arr[child], arr[parent]);parent = child;int child = parent * 2 + 1;}elsereturn;}}
};
int main()
{vector<int> arr = { 4,5,1,6,2,7,3,8 };// Sort::QuickSort(arr, 0, arr.size());// Sort::MergeSort(arr, 0, arr.size());Sort::HeapSort(arr, 0, arr.size());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！