六種排序與兩種查找算法
一 排序算法 (此處的排序均為升序排列)
???排序算法總的來說可以分成內(nèi)部排序和外部排序 (內(nèi)外是相對內(nèi)存而言的,對于內(nèi)部排序算法,它需要將數(shù)據(jù)全部加載入內(nèi)存,才可以進(jìn)行排序,而外部排序可以將數(shù)據(jù)分批加載進(jìn)入內(nèi)存,進(jìn)行排序,比如:歸并排序);
????此外排序算法還可以分為穩(wěn)定排序和非穩(wěn)定排序 (若之前A(i) == A(j) && i < j,那么在排序之后A(i)依舊在A(j)的前面,此時我們稱該排序算法是穩(wěn)定的)。
????穩(wěn)定排序有:插入排序,冒泡排序,歸并排序
????非穩(wěn)定排序有:選擇排序,快速排序, 堆排序, 希爾排序
穩(wěn)定排序
1. 插入排序
???正如口訣所說的那樣,我們將數(shù)組分為已排序和未排序兩部分,我們要做的就是把已排序區(qū)域后面的一個元素插入到前面已排序區(qū)域的恰當(dāng)位置,這樣直到數(shù)組有序,算法結(jié)束
???對應(yīng)的實現(xiàn)代碼為:
void insert_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
swap(arr[j], arr[j - 1]);
}
}
}
2. 冒泡排序
???冒泡排序同樣是將數(shù)組分成已排序和未排序兩部分,其中已排序的部分是在數(shù)組的后方 (注意區(qū)分這和插入和選擇排序是不同的),我們要做的就是在前面沒有排序的部分中,找到最大的一個元素 (通過不斷的交換實現(xiàn)),并將該元素放在已排序部分的前面,如此循環(huán),直至未排序部分的元素個數(shù)為0,此時算法結(jié)束
???對應(yīng)的代碼為:
void bubble_sort(int *arr, int n) {
for (int i = 1; i < n; i++) {
int flag = 0;
for (int j = 0; j < n - i; j++) {
if (arr[j] <= arr[j + 1]) continue;
swap(arr[j], arr[j + 1]);
flag = 1;
}
if (!flag) break;
}
}
???此時需要注意的是:存在這樣的一種情況,在內(nèi)部循環(huán)中并沒有進(jìn)行交換,也就是說,此時數(shù)組已經(jīng)有序,不需要再排序,直接退出即可,為此我們引入標(biāo)記位flag,當(dāng)存在交換時flag = 1,若一次內(nèi)部循環(huán)之后,flag沒有改變,此時直接跳出循環(huán),算法結(jié)束。
3. 歸并排序
? ???歸并排序是目前自己知曉的最快的穩(wěn)定排序,并且重要的是它的時間復(fù)雜度穩(wěn)定在O(N * log N),歸并排序充分的利用了分治的思想,將原來的數(shù)組對半劃分,并分別對這兩個子數(shù)組進(jìn)行排序,如此不斷的遞歸下去,當(dāng)子數(shù)組的只有一個或兩個元素的時候,此時我們可以處理 (這也是遞歸的出口),之后我們將數(shù)組之間兩兩之間合并 (只需要兩個指針就可實現(xiàn)),這樣我們就可以使整個數(shù)組有序了。
? ???我們將數(shù)組劃分為兩個子數(shù)組,但其實這只是一種,我們稱之為2路歸并,除此之外,我們還有多路歸并,只不過這樣排序后合并數(shù)組就會比之前麻煩
? ???歸并排序還有一個重要的性質(zhì):那就是可以實現(xiàn)外部排序,這個算法本身實現(xiàn)的過程有關(guān),比如對于一個32G的數(shù)據(jù)文件,顯然我們不可以全部加載進(jìn)內(nèi)存,因此我們可以分8次,每次載入4G的數(shù)據(jù)進(jìn)行排序,之后我們得到8個部分有序的子數(shù)組,剩下的就是不斷地讀取數(shù)組,將他們合并到一塊(我們可以將兩個排好序的4G的數(shù)據(jù)文件,各讀取一部分進(jìn)入內(nèi)存,邊合并邊將數(shù)據(jù)不斷的寫到外存里面)
實現(xiàn)代碼如下:
void merge_sort(int *arr, int head, int tail) {
if (tail - head <= 1) {
if (tail - head == 1 && arr[head] > arr[tail]) {
swap(arr[head], arr[tail]);
}
return ;
}
int mid = (head + tail) >> 1;
merge_sort(arr, head, mid);
merge_sort(arr, mid + 1, tail);
int *num = (int *)malloc(sizeof(int) * (tail - head + 1));
int p1 = head, p2 = mid + 1, ind = 0;
while (p1 <= mid || p2 <= tail) {
if (p2 > tail || (p1 <= mid && arr[p1] <= arr[p2])) {
num[ind++] = arr[p1++];
} else {
num[ind++] = arr[p2++];
}
}
memcpy(arr + l, num, sizeof(int) * (tail - head + 1));
free(num);
}
其中對于兩個子數(shù)組的合并,感覺判斷條件之間存在交叉和部分獨立,但是不影響最后的結(jié)果
不穩(wěn)定排序
1. 選擇排序?
??選擇排序?qū)?shù)組分為已排序和未排序兩部分,我們要做的就是在后面未排序的數(shù)組中找到最小的一個元素,將他放在已排序部分的后面,如此循環(huán),直到未排序部分元素的個數(shù)為0,算法結(jié)束。
???實現(xiàn)代碼如下:
void select_sort(int *arr, int n) {
for (int i = 0; i < n - 1; i++) {
int ind = i;
for (int j = i; j < n; j++) {
if (arr[i] < arr[ind]) ind = i;
}
if (ind == i) continue;
swap(arr[ind], arr[i]);
}
}
2. 快速排序
???快排算法的基本思路就是選取基本元素,并根據(jù)首尾兩個指針將數(shù)組分成兩部分,其中前面部分?jǐn)?shù)據(jù)均小于基準(zhǔn)元素,后面部分均大于基準(zhǔn)元素,之后繼續(xù)對劃分后的兩個子數(shù)組進(jìn)行劃分即可。
???注意:首先前移的一定是尾指針,之后再首尾指針相互移動
???對應(yīng)代碼為:
void quick_sort(int *arr, int l, int r) {
if (l > r) return ;
int head = l, tail = r, tmp = arr[head];
while (head != tail) {
while (head < tail && arr[tail] >= tmp) tail--;
while (head < tail && arr[head] <= tmp) head++;
if (tail != head) {
swap(arr[head], arr[tail]);
}
}
arr[l] = arr[head];
arr[head] = tmp;
quick_sort(arr, l, head - 1);
quick_sort(arr, head + 1, r);
}
???快排算法的時間復(fù)雜性雖然為(n * log n),但是他并不穩(wěn)定,當(dāng)數(shù)組是逆序排列時,此時會退化成冒泡排序時間復(fù)雜度變?yōu)镺(n * n),所以基準(zhǔn)值的選取十分重要,這回直接影響算法的效率,為此,我們可以優(yōu)化為隨機(jī)化快排,也就是將最壞事件轉(zhuǎn)換為概率事件,我們在數(shù)組中隨即選擇數(shù)字作為劃分基準(zhǔn),所以,算法的一般時間復(fù)雜性依舊為O(n * log n);
二 查找算法
1. 二分查找
???之前最普通的查找算法就是在一個有序的數(shù)組中,找到待查找數(shù)字的下標(biāo),若找不到則返回-1
對應(yīng)代碼如下:
void binarySearch(int *arr, int n, int x) {
int head = 0, tail = n - 1, mid;
while (head <= tail) {
mid = (head + tail) >> 1;
if (arr[mid] == x) return mid;
else if (arr[mid] < head) head = mid + 1;
else tail = mid - 1;
}
return -1
}
此外,二分查找還有兩種特殊的情況,如下:
???在如1111110000000的數(shù)組中,找到最后一個1,首先我們了解max和min是如何變化的,之后我們來考慮一種情況:那就是當(dāng)這是一個全0的序列,程序結(jié)束后min和max均會指向下標(biāo)為0的元素,所以程序最后的返回將會是0,但這顯然是錯誤的,為了解決這個問題,我們引入了一個虛擬頭指針,一開始min指向 -1,現(xiàn)在我們來解釋為什么mid = (min + max + 1) >> 2,而不是mid = (min + max) >> 1,因為存在這樣一種情況,當(dāng)最后min和max指向相鄰的兩個元素時,此時求mid之后,會陷入死循環(huán)中,程序無法跳出循環(huán)。最后需要注意的是:函數(shù)最后返回的是head的值,也就是最后一個1所在的下標(biāo),此外有實際出發(fā)推演,while循環(huán)的條件是min < max沒有等號。
???第二種特殊情況,這里就不再多說,相似理解,我們直接上代碼
void binarySearch_2(int *arr, int n) { //找到最后一個1所在的下標(biāo)
int head = -1, tail = n - 1, mid;
while (head < tail) {
mid = (head + tail + 1) >> 1;
if (arr[mid] == 1) head = mid;
else tail = mid - 1;
}
return head;
}
void binarySearch_3(int *arr, int n) { //找到第一個1所在的下標(biāo)
int head = 1, tail = n, mid;
while (head < tail) {
mid = (head + tail) >> 1;
if (arr[mid] == 1) tail = mid;
else head = mid + 1;
}
return head == n ? -1 : head;
}
???擴(kuò)大來說,這里的1并不僅僅是1,其實更多指的是一種性質(zhì),我們要找的是找到第一個或者是最后一個滿足這種性質(zhì)的元素下標(biāo),這樣我們可以避免使用低效的線性搜索,可以使用更高效的二分查找。
- 三分查找
?三分查找這里我們用來求的是二次函數(shù)極值點的問題,當(dāng)然對于這個問題我們還可以用求導(dǎo),使用牛頓迭代法進(jìn)行求解
三 總代碼獻(xiàn)上
穩(wěn)定排序
#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;
//穩(wěn)定排序有:插入排序,冒泡排序,歸并排序
#define swap(a, b) { \ //宏定義 交換a和b的值
__typeof(a) __tmp = a; a = b, b = __tmp; }
#define TEST(arr, n, func, args...) { \ //宏定義 調(diào)用排序函數(shù)并打印輸出
int *num = (int *)malloc(sizeof(int) * n); memcpy(num, arr, sizeof(int) * n); printf("%s:\n", #func); output(num, n); func(args); output(num, n); printf("\n"); free(num); }
void insert_sort(int *arr, int n) { //插入排序
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
swap(arr[j - 1], arr[j]);
}
}
}
void bubble_sort(int *arr, int n) { //冒泡排序
for (int i = 1; i < n; i++) {
int flag = 0;
for (int j = 0; j < n - i; j++) {
if (arr[j] <= arr[j + 1]) continue;
swap(arr[j], arr[j + 1]);
flag = 1;
}
if (!flag) break;
}
}
void merge_sort(int *arr, int head, int tail) { //歸并排序
if (tail - head <= 1) {
if (tail - head == 1 && arr[head] > arr[tail]) {
swap(arr[head], arr[tail]);
}
return ;
}
int mid = (head + tail) >> 1;
merge_sort(arr, head, mid);
merge_sort(arr, mid + 1, tail);
int *num = (int *)malloc(sizeof(int) * (tail - head + 1));
int p1 = head, p2 = mid + 1, ind = 0;
while (p1 <= mid || p2 <= tail) {
if (p2 > tail || (p1 <= mid && arr[p1] <= arr[p2])) {
num[ind++] = arr[p1++];
} else {
num[ind++] = arr[p2++];
}
}
memcpy(arr + head, num, sizeof(int) * (tail - head + 1));
free(num);
}
void output(int *arr, int n) {
printf("[");
for (int i = 0; i < n; i++) {
if (i) printf(", ");
printf("%d", arr[i]);
}
printf("]\n");
}
void randInt(int *a, int n) {
while (n--) a[n] = rand() % 100;
}
int main() {
#define MAX_N 20
srand(time(0));
int arr[MAX_N] = {0};
randInt(arr, MAX_N);
TEST(arr, MAX_N, insert_sort, num, MAX_N);
TEST(arr, MAX_N, bubble_sort, num, MAX_N);
TEST(arr, MAX_N, merge_sort, num, 0, MAX_N - 1);
return 0;
}
/* 對應(yīng)輸出
insert_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]
bubble_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]
merge_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]
*/
非穩(wěn)定排序
#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;
#define swap(a, b) { __typeof(a) __tmp = a; a = b, b = __tmp; }
#define TEST(arr, n, func, args...) { int *num = (int *)malloc(sizeof(int) * n); memcpy(num, arr, sizeof(int) * n); printf("%s:\n", #func); output(num, n); func(args); output(num, n); printf("\n"); free(num); }
void select_sort(int *arr, int n) { //選擇排序
for (int i = 0; i < n - 1; i++) {
int ind = i;
for (int j = i; j < n; j++) {
if (arr[j] < arr[ind]) ind = j;
}
if (ind == i) continue;
swap(arr[ind], arr[i]);
}
}
void quick_sort(int *arr, int head, int tail) { //快排
if (head > tail) return ;
int left = head, right = tail;
int tmp = arr[head];
while (left != right) {
while (left < right && arr[right] >= tmp) right--;
while (left < right && arr[left] <= tmp) left++;
if (left != right) swap(arr[left], arr[right]);
}
arr[head] = arr[left];
arr[left] = tmp;
quick_sort(arr, head, left - 1);
quick_sort(arr, left + 1, tail);
}
void randInt(int *arr, int n) {
while (n--) arr[n] = rand() % 100;
}
void output(int *arr, int n) {
printf("[");
for (int i = 0; i < n; i++) {
if (i) printf(", ");
printf("%d", arr[i]);
}
printf("]\n");
}
int main() {
#define MAX_N 20
srand(time(0));
int arr[MAX_N];
randInt(arr, MAX_N);
TEST(arr, MAX_N, select_sort, num, MAX_N)
TEST(arr, MAX_N, quick_sort, num, 0, MAX_N - 1)
return 0;
}
/* 代碼輸出
select_sort:
[2, 89, 16, 82, 58, 73, 61, 91, 59, 79, 18, 62, 81, 70, 31, 89, 82, 46, 27, 71]
[2, 16, 18, 27, 31, 46, 58, 59, 61, 62, 70, 71, 73, 79, 81, 82, 82, 89, 89, 91]
quick_sort:
[2, 89, 16, 82, 58, 73, 61, 91, 59, 79, 18, 62, 81, 70, 31, 89, 82, 46, 27, 71]
[2, 16, 18, 27, 31, 46, 58, 59, 61, 62, 70, 71, 73, 79, 81, 82, 82, 89, 89, 91]
*/
二分查找
#include <iostream>
using namespace std;
#define P(func, args...) { printf("%s = %d\n", #func, func(args)); }
int binarySearch_1(int *arr, int n, int x) {
int head = 0, tail = n - 1, mid;
while (head <= tail) {
mid = (head + tail) >> 1;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) head = mid + 1;
else tail = mid - 1;
}
return -1;
}
//1111100000 找到最后一個1
int binarySearch_2(int *arr, int n) {
int head = -1, tail = n - 1;
while (head < tail) {
int mid = (head + tail + 1) >> 1;
if (arr[mid] == 1) head = mid;
else tail = mid - 1;
}
return head;
}
//000000111111找到第一個1
int binarySearch_3(int *arr, int n) {
int head = 0, tail = n, mid;
while (head < tail) {
mid = (head + tail) >> 1;
if (arr[mid] == 1) tail = mid;
else head = mid + 1;
}
return head == n ? -1 : head;
}
int main() {
int arr1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int arr2[10] = {1, 1, 1, 1, 1, 1, 1, 1, 0, 0};
int arr3[10] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1};
printf("num %d's index = %d\n", 7, binarySearch_1(arr1, 10, 7));
P(binarySearch_2, arr2, 10);
P(binarySearch_3, arr3, 10);
return 0;
}
/* 對應(yīng)輸出為:
num 7's index = 6
binarySearch_2 = 7
binarySearch_3 = 7
*/
|