1. 應用場景

a.有兩個長度分別為m和n的未排序int數(shù)組A和B
b.請寫一個func將兩個數(shù)組的進行排序?qū)⒆钚〉膍個int以從小到大的順序存儲在數(shù)組A, 最大的n個數(shù)以從小到到的順序存儲在數(shù)組B
注意：m, n的長度可能很大所以請注意空間使用情況

例子：
轉(zhuǎn)換前：
a := [98, 67, 91, 99, 13]
b := [97, 35, 88]

轉(zhuǎn)換后：
a := [13, 35, 67, 88, 91]
b := [97, 98, 99]

2. 使用快速排序，把兩個組成當成一個數(shù)組。

#include <random>int m = 0;int n = 0;int getValue(int A[], int B[], int i) {if (i < 0)i = 0;if (i >= m + n)i = m + n - 1;if (i < m)return A[i];elsereturn B[i - m];}void setValue(int A[], int B[], int i, int value) {if (i < 0)i = 0;if (i >= m + n)i = m + n - 1;if (i < m)A[i] = value;elseB[i - m] = value;}void swap(int A[], int B[], int low, int high) {int a = getValue(A, B, low);int b = getValue(A, B, high);setValue(A, B, low, b);setValue(A, B, high, a);}int parititionArray(int A[], int B[], int low, int high) {int pivot_idx = low + rand() % (high - low + 1); // randomly select// move pivot to beginswap(A, B, pivot_idx, low);int pivot = getValue(A, B, low);while (low < high) {while (low < high && getValue(A, B, high) >= pivot) {--high;}setValue(A, B, low, getValue(A, B, high));while (low < high && getValue(A, B, low) <= pivot) {++low;}setValue(A, B, high, getValue(A, B, low));}setValue(A, B, low, pivot);return low;}void quickSortArray(int A[], int B[], int low, int high){if (low < high) {int pivot = parititionArray(A, B, low, high);quickSortArray(A, B, 0, pivot - 1);quickSortArray(A, B, pivot + 1, high);}}void quickSort() {int a[] = { 98, 67, 391, 99, 13, 130 };int b[] = { 97, 35, 88, 120, 140 };m = sizeof(a) / sizeof(int);n = sizeof(b) / sizeof(int);quickSortArray(a, b, 0, m + n - 1);int i = 4;}
【引用】

[1] 代碼quickSort.h

總結(jié)

以上是生活随笔為你收集整理的排序 （2）快速排序-多个数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。