title: 排序
date: 2022-08-18 11:54:40
tags:
- 数据结构
categories:
- 408
- 数据结构
- 代码
顺寻存储————随机访问
链式存储————顺序访问
快排
Leecode:
class Solution {
int randomized_partition(vector<int>& nums, int l, int r) {
int q = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums[r], nums[q]);
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]);
return i + 1;
}
void randomized_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int pos = randomized_partition(nums, l, r);
randomized_quicksort(nums, l, pos - 1);
randomized_quicksort(nums, pos + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
randomized_quicksort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
非随机快排:
#include <iostream>
#include <vector>
using namespace std;
//第一个元素为pivot
int partition(int a[], int l, int r){
int pivot = a[l]; //设表中第一个元素为pivot
while (l < r)
{
while(l < r && a[r] >= pivot) r--; //如果r大于pivot，指针左移
a[l] = a[r]; //r < povot交换lr位置
while(l < r && a[l] <= pivot) l++;
a[r] = a[l];
}
a[l] = pivot;
return l;
}
void quicksort(int a[],int l, int r){
if(l < r){
int pos = partition(a, l, r);
quicksort(a, l, pos-1);
quicksort(a, pos + 1, r);
}
}
int main(int argc, char const *argv[])
{
int arr[] = {5, 2, 3, 1};
quicksort(arr, 0, sizeof(arr)/sizeof(int) - 1);
for (int i = 0; i < sizeof(arr)/sizeof(int); i++)
{
printf("%d ",arr[i]);
}
return 0;
}
随机pivot快排
#include <iostream>
#include <vector>
using namespace std;
/**
* @description: 划分操作，将未排序数组划分为左， pivot，右
* @param {int} a 数组
* @param {int} l 最小下标
* @param {int} r 最大下标
* @return {*} pivot
*/
int partition(int a[], int l, int r){
int pivot = a[l]; //设表中第一个元素为pivot
while (l < r)
{
while(l < r && a[r] >= pivot) r--; //如果r大于pivot，指针左移
a[l] = a[r]; //r < povot交换lr位置
while(l < r && a[l] <= pivot) l++;
a[r] = a[l];
}
a[l] = pivot;
return l;
}
/**
* @description: 随机划分
* @param {int} a 数组
* @param {int} l 最小下标
* @param {int} r 最大下标
* @return {*}
*/
int randomized_partition(int a[], int l, int r){
int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元，(r-l)防止溢出
swap(a[l], a[i]);
return partition(a, l, r);
}
/**
* @description: 递归快排
* @param {int} a 数组
* @param {int} l 最小下标
* @param {int} r 最大下标
* @return {*} null
*/
void randomized_quicksort(int a[],int l, int r){
if(l < r){
int pos = randomized_partition(a, l, r);
randomized_quicksort(a, l, pos-1);
randomized_quicksort(a, pos + 1, r);
}
}
int main(int argc, char const *argv[])
{
//int arr[] = {5,1,1,2,0,0};
int arr[] = {5,2,3,1,2};
randomized_quicksort(arr, 0, sizeof(arr)/sizeof(int) - 1);
for (int i = 0; i < sizeof(arr)/sizeof(int); i++)
{
printf("%d ",arr[i]);
}
return 0;
}
归并
Leecode:
class Solution {
vector<int> tmp;
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
}
else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= r) {
tmp[cnt++] = nums[j++];
}
for (int i = 0; i < r - l + 1; ++i) {
nums[i + l] = tmp[i];
}
}
public:
vector<int> sortArray(vector<int>& nums) {
tmp.resize((int)nums.size(), 0);
mergeSort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
My:
#include <iostream>
#include <vector>
using namespace std;
void merge(int arr[], int tempArr[], int left, int mid, int right)
{
// 标记左半区第一个未排序的元素
int l_pos = left;
// 标记右半区第一个未排序的元素
int r_pos = mid + 1;
// 临时数组元素的下标
int pos = left;
// 合并
while (l_pos <= mid && r_pos <= right)
{
if (arr[l_pos] < arr[r_pos]) // 左半区第一个剩余元素更小
tempArr[pos++] = arr[l_pos++];
else // 右半区第一个剩余元素更小
tempArr[pos++] = arr[r_pos++];
}
// 合并左半区剩余的元素
while (l_pos <= mid)
tempArr[pos++] = arr[l_pos++];
// 合并右半区剩余的元素
while (r_pos <= right)
tempArr[pos++] = arr[r_pos++];
// 把临时数组中合并后的元素复制回原来的数组
while (left <= right)
{
arr[left] = tempArr[left];
left++;
}
}
// 归并排序
void msort(int arr[], int tempArr[], int left, int right)
{
// 如果只有一个元素，那么不需要继续划分
// 只有一个元素的区域，本生就是有序的，只需要被归并即可
if (left < right)
{
// 找中间点
int mid = (left + right) / 2;
// 递归划分左半区
msort(arr, tempArr, left, mid);
// 递归划分右半区
msort(arr, tempArr, mid + 1, right);
// 合并已经排序的部分
merge(arr, tempArr, left, mid, right);
}
}
// 归并排序入口
void merge_sort(int arr[], int n)
{
// 分配一个辅助数组
int tempArr[n];
// 调用实际的归并排序
msort(arr, tempArr, 0, n - 1);
}
void print_arr(int a[], int n){
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main(int argc, char const *argv[])
{
int a[] = {49, 38, 65, 97, 76, 13, 27};
int n = sizeof(a)/sizeof(int);
print_arr(a, n);
merge_sort(a, n);
print_arr(a, n);
return 0;
}
堆排
class Solution {
void maxHeapify(vector<int>& nums, int i, int len) {
for (; (i << 1) + 1 <= len;) {
int lson = (i << 1) + 1;
int rson = (i << 1) + 2;
int large;
if (lson <= len && nums[lson] > nums[i]) {
large = lson;
} else {
large = i;
}
if (rson <= len && nums[rson] > nums[large]) {
large = rson;
}
if (large != i) {
swap(nums[i], nums[large]);
i = large;
} else {
break;
}
}
}
void buildMaxHeap(vector<int>& nums, int len) {
for (int i = len / 2; i >= 0; --i) {
maxHeapify(nums, i, len);
}
}
void heapSort(vector<int>& nums) {
int len = (int)nums.size() - 1;
buildMaxHeap(nums, len);
for (int i = len; i >= 1; --i) {
swap(nums[i], nums[0]);
len -= 1;
maxHeapify(nums, 0, len);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
heapSort(nums);
return nums;
}
};