前言
本文是題主準(zhǔn)備面試時記錄下的筆記整理而來毙驯，稍顯粗陋倒堕，還請各位擼友勿噴哈！
Topic
-
目錄
-
目標(biāo)
- 熟練使用常用數(shù)據(jù)結(jié)構(gòu)的基本操作
- 加深對常用算法與技巧的理解
- 面試
-
參考
- 《程序員面試金典》
- 《劍指offer》
- Leetcode
- 《結(jié)構(gòu)之法 --July》
排序篇
1_1.BubbleSort
//冒泡排序
static void BubbleSort(vector<int> &v){
int len = v.size(), flag; //數(shù)組長度 & 交換標(biāo)記變量
for(int i = 0; i < len; ++i){
flag = 0; //初始化標(biāo)記為0
for(int j = 1; j < len - i; ++j){
if(v[j - 1] > v[j]){
swap(v[j - 1],v[j]);
flag = 1; //發(fā)生交換爆价，標(biāo)記變量置1
}
}
if(flag == 0) //一輪比較后垦巴，如未發(fā)生交換，說明已排好序
break;
}
}
1_2.SelectSort
//選擇排序
static void SelectSort(vector<int> &v){
int len = v.size(), min_idx; //數(shù)組長度 & 無序區(qū)最小元素位置
for(int i = 0; i < len; ++i){ //i：無序區(qū)中開頭位置
min_idx = i;
//尋找無序區(qū)中最小元素的位置
for(int j = i + 1; j < len; ++j){
if(v[min_idx] > v[j])
min_idx = j;
}
//最小元素位置如不等于i铭段，則交換位置
if(min_idx != i){
swap(v[min_idx], v[i]);
}
}
}
1_3.InsertSort
//插入排序
static void InsertSort(vector<int> &v){
int len = v.size(), tmp, i, j;
for(i = 1; i < len; ++i){
tmp = v[i];
for(j = i; j > 0 && tmp < v[j - 1]; --j)
v[j] = v[j - 1];
v[j] = tmp;
}
}
1_4.ShellSortSh
//希爾排序(希爾增量)
static void ShellSortSh(vector<int> &v){
int len = v.size();
int gap, i, j, tmp;
/* 形式一 */
for(gap = len / 2; gap > 0; gap /= 2){
//里面兩層循環(huán)是實(shí)現(xiàn)插排的代碼
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
/* 形式二:
//初始化最大步長
for(gap = 1; gap <= (len - 1) / 4; gap = 2 * gap); //普林斯頓大學(xué)給出的寫法
for(; gap > 0; gap /= 2){
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
*/
}
1_5.ShellSortKn
//希爾排序(Knuth增量)
static void ShellSortKn(vector<int> &v){
int len = v.size();
int gap, i, j, tmp;
//初始化最大步長
//for(gap = 1; gap <= (len - 1) / 9; gap = 3 * gap + 1); //普林斯頓大學(xué)給出的寫法
for(gap = 1; gap < len / 3; gap = 3 * gap + 1);
for(; gap > 0; gap /= 3){
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
}
1_6.MergeSortUp2Down
1_7.MergeSortDown2Up
//歸并排序外部接口
static void IMergeSort(vector<int> &v){
int len = v.size();
MergeSortUpToDown(v, 0, len - 1);
//MergeSortDownToUp(v, len);
}
//自頂向下歸并排序?qū)崿F(xiàn)
static void MergeSortUpToDown(vector<int> &v, int start, int end){
if(start < end){
int mid = (start + end) / 2;
//遞歸分解
MergeSortUpToDown(v, start, mid);
MergeSortUpToDown(v, mid + 1, end);
//合并
Merge(v, start, mid, end);
}
}
//歸并實(shí)現(xiàn)關(guān)鍵代碼
static void Merge(vector<int> &v, int start, int mid, int end){
//初始化臨時數(shù)組
vector<int> tmp( v.size() );
//初始化位置坐標(biāo)
int leftPos = start, leftEnd = mid;
int rightPos = mid + 1, rightEnd = end;
int tmpPos = leftPos;
int numElement = end - start + 1;
//歸并主實(shí)現(xiàn)
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(v[leftPos] <= v[rightPos])
tmp[tmpPos++] = v[leftPos++];
else
tmp[tmpPos++] = v[rightPos++];
}
//拷貝左半段剩余的的元素
while(leftPos <= leftEnd)
tmp[tmpPos++] = v[leftPos++];
//拷貝右半段剩余的元素
while(rightPos <= rightEnd)
tmp[tmpPos++] = v[rightPos++];
//拷貝回原數(shù)組
//for(int i = rightEnd; i >= start; --rightEnd){
for(int i = 0; i < numElement; ++i, --rightEnd){
v[rightEnd] = tmp[rightEnd];
}
}
//自底向上歸并排序?qū)崿F(xiàn)
static void MergeSortDownToUp(vector<int> &v, int len){
/* 拆分版：遍歷實(shí)現(xiàn)相鄰兩組的元素進(jìn)行歸并排序
for(int gap = 1; gap < len; gap *= 2){
mergeGroups(v, len, gap);
}
*/
/* 合并版 */
int i;
//遍歷實(shí)現(xiàn)相鄰兩組的元素進(jìn)行歸并排序
for(int gap = 1; gap < len; gap *= 2){
//相鄰的子數(shù)組歸并排序的主實(shí)現(xiàn)
for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
Merge(v, i, i + gap - 1, i + 2 * gap - 1);
}
//組數(shù)為奇數(shù)時骤宣，剩余一個組未配對
if(i + gap - 1 < len){
Merge(v, i, i + gap - 1, len - 1);
}
}
}
//分組合并排序?qū)崿F(xiàn)（將相鄰的子數(shù)組進(jìn)行合并排序）
static void mergeGroups(vector<int> &v, int len, int gap){
int i;
//相鄰的子數(shù)組歸并排序的主實(shí)現(xiàn)
for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
Merge(v, i, i + gap - 1, i + 2 * gap - 1);
}
//組數(shù)為奇數(shù)時，剩余一個組未配對
if(i + gap - 1 < len){
Merge(v, i, i + gap - 1, len - 1);
}
}
1_8.HeapSort
//堆排序
static void HeapSort(vector<int> &v){
int len = v.size();
//建立初始堆
for(int i = len / 2; i >= 0; --i){
percDown(v, i, len);
}
//deleteMax
for(int j = len - 1; j > 0; --j){
swap(v[0], v[j]);
percDown(v, 0, j);
}
}
//堆排序下濾實(shí)現(xiàn)
static void percDown(vector<int> &v, int iter, int len){
int child;
int tmp = v[iter]; //create hole
for( ; 2 * iter + 1 < len; iter = child){
child = 2 * iter + 1; //獲取該節(jié)點(diǎn)的左孩子下標(biāo)
//如有右孩子序愚，且右孩子大于左孩子憔披，下標(biāo)改成右孩子下標(biāo)
if(child != len - 1 && v[child] < v[child + 1] )
child++;
//孩子結(jié)點(diǎn)值大于該結(jié)點(diǎn)值，則下濾
if(tmp < v[child])
v[iter] = v[child];
else //否則展运，說明結(jié)點(diǎn)處于正確位置活逆，可跳出循環(huán)
break;
}
v[iter] = tmp; //把hole堵上
}
1_9.QuickSort
//快速排序
static void QuickSort(vector<int> &v){
QuickSortRecursion(v, 0, v.size() - 1);
}
static void QuickSortRecursion(vector<int> &v, int left, int right){
/* 優(yōu)化做法 */
if(left + 5 <= right){
int pivot = getPivot(v, left, right);
int front = left;
int rear = right - 1;
//int front = left + 1;
//int rear = right - 2;
while(1){
while(v[++front] < pivot){ }
while(v[--rear] > pivot){ }
if(front < rear)
swap(v[front], v[rear]);
else
break;
}
swap(v[front], v[right - 1]);
QuickSortRecursion(v, left, front - 1); //sort small elements
QuickSortRecursion(v, front + 1, right); //sort large elements
}
else{
InsertSortForQSort(v, left, right);
}
/* 純快排做法
if(right - left <= 1){ //遞歸出口精刷，小于兩個元素情況的處理
if(v[left] > v[right])
swap(v[left],v[right]);
return;
}
int pivot = getPivot(v, left, right); //樞紐元
int front = left;
int rear = right - 1;
while(1){
//首尾指針向中間靠攏
while(v[++front] < pivot){ }
while(v[--rear] > pivot){ }
//front小于rear則交換元素
if(front < rear)
swap(v[front], v[rear]);
else
break; //front、rear交錯蔗候，則不再交換怒允，跳出循環(huán)
}
swap(v[front], v[right - 1]); //將樞紐元放到正確位置
QuickSortRecursion(v, left, front - 1); //sort small elements
QuickSortRecursion(v, front + 1, right); //sort large elements
*/
}
//三數(shù)中值取樞紐元
static int getPivot(vector<int> &v, int left, int right){
int mid = (left + right) / 2;
if(v[left] > v[mid])
swap(v[left], v[mid]);
if(v[left] > v[right])
swap(v[left],v[right]);
if(v[mid] > v[right])
swap(v[mid], v[right]);
swap(v[mid], v[right - 1]);
return v[right - 1];
}
//適配快排的插入排序
static void InsertSortForQSort(vector<int> &v,int left, int right){
int tmp, i, j;
for(i = left + 1; i <= right; ++i){
tmp = v[i];
for(j = i; j >= left && tmp < v[j - 1]; --j)
v[j] = v[j - 1];
v[j] = tmp;
}
}
類代碼
/*************************************************************************
> File Name: sort.h
> Description:
（1）實(shí)現(xiàn)常用的各種排序
（2）利用回調(diào)函數(shù)實(shí)現(xiàn)
> Conclusion:
> Author: rh_Jameson
> Created Time: 2015年03月06日 星期五 20時33分45秒
************************************************************************/
#ifndef _SORT_H
#define _SORT_H
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
//字符串?dāng)?shù)組，通過該數(shù)組適配switch
static string sort_type[] = {"BubbleSort", "SelectSort", "InsertSort",
"ShellSortSh", "ShellSortKn", "IMergeSort",
"HeapSort","QuickSort"
};
class Sort {
public:
//Sort構(gòu)造函數(shù)
Sort(vector<int> &v, string sort_name){
if(v.empty()){
cout << "數(shù)組為空" << endl;
return;
}
int len = 8, i;
//判斷要采取何種排序
for(i = 0; i < len; ++i){
if(sort_name == sort_type[i]){
break;
}
}
switch(i){
case 0: CallSort = BubbleSort; break;
case 1: CallSort = SelectSort; break;
case 2: CallSort = InsertSort; break;
case 3: CallSort = ShellSortSh; break;
case 4: CallSort = ShellSortKn; break;
case 5: CallSort = IMergeSort; break;
case 6: CallSort = HeapSort; break;
case 7: CallSort = QuickSort; break;
default: cout << "無此排序锈遥！" << endl; return;
}
CallSort(v);
}
//兩數(shù)交換函數(shù)
static void swap(int &num1, int &num2){
int tmp = num1;
num1 = num2;
num2 = tmp;
}
//冒泡排序
static void BubbleSort(vector<int> &v){
int len = v.size(), flag; //數(shù)組長度 & 交換標(biāo)記變量
for(int i = 0; i < len; ++i){
flag = 0; //初始化標(biāo)記為0
for(int j = 1; j < len - i; ++j){
if(v[j - 1] > v[j]){
swap(v[j - 1],v[j]);
flag = 1; //發(fā)生交換纫事，標(biāo)記變量置1
}
}
if(flag == 0) //一輪比較后，如未發(fā)生交換所灸，說明已排好序
break;
}
}
//選擇排序
static void SelectSort(vector<int> &v){
int len = v.size(), min_idx; //數(shù)組長度 & 無序區(qū)最小元素位置
for(int i = 0; i < len; ++i){ //i：無序區(qū)中開頭位置
min_idx = i;
//尋找無序區(qū)中最小元素的位置
for(int j = i + 1; j < len; ++j){
if(v[min_idx] > v[j])
min_idx = j;
}
//最小元素位置如不等于i丽惶，則交換位置
if(min_idx != i){
swap(v[min_idx], v[i]);
}
}
}
//插入排序
static void InsertSort(vector<int> &v){
int len = v.size(), tmp, i, j;
for(i = 1; i < len; ++i){
tmp = v[i];
for(j = i; j > 0 && tmp < v[j - 1]; --j)
v[j] = v[j - 1];
v[j] = tmp;
}
}
//希爾排序(希爾增量)
static void ShellSortSh(vector<int> &v){
int len = v.size();
int gap, i, j, tmp;
/* 形式一 */
for(gap = len / 2; gap > 0; gap /= 2){
//里面兩層循環(huán)是實(shí)現(xiàn)插排的代碼
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
/* 形式二:
//初始化最大步長
for(gap = 1; gap <= (len - 1) / 4; gap = 2 * gap); //普林斯頓大學(xué)給出的寫法
for(; gap > 0; gap /= 2){
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
*/
}
//希爾排序(Knuth增量)
static void ShellSortKn(vector<int> &v){
int len = v.size();
int gap, i, j, tmp;
//初始化最大步長
//for(gap = 1; gap <= (len - 1) / 9; gap = 3 * gap + 1); //普林斯頓大學(xué)給出的寫法
for(gap = 1; gap < len / 3; gap = 3 * gap + 1);
for(; gap > 0; gap /= 3){
for(i = gap; i < len; ++i){
tmp = v[i];
for(j = i; j >= gap && tmp < v[j - gap]; j -= gap)
v[j] = v[j - gap];
v[j] = tmp;
}
}
}
//歸并排序外部接口
static void IMergeSort(vector<int> &v){
int len = v.size();
MergeSortUpToDown(v, 0, len - 1);
//MergeSortDownToUp(v, len);
}
//自頂向下歸并排序?qū)崿F(xiàn)
static void MergeSortUpToDown(vector<int> &v, int start, int end){
if(start < end){
int mid = (start + end) / 2;
//遞歸分解
MergeSortUpToDown(v, start, mid);
MergeSortUpToDown(v, mid + 1, end);
//合并
Merge(v, start, mid, end);
}
}
//歸并實(shí)現(xiàn)關(guān)鍵代碼
static void Merge(vector<int> &v, int start, int mid, int end){
//初始化臨時數(shù)組
vector<int> tmp( v.size() );
//初始化位置坐標(biāo)
int leftPos = start, leftEnd = mid;
int rightPos = mid + 1, rightEnd = end;
int tmpPos = leftPos;
int numElement = end - start + 1;
//歸并主實(shí)現(xiàn)
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(v[leftPos] <= v[rightPos])
tmp[tmpPos++] = v[leftPos++];
else
tmp[tmpPos++] = v[rightPos++];
}
//拷貝左半段剩余的的元素
while(leftPos <= leftEnd)
tmp[tmpPos++] = v[leftPos++];
//拷貝右半段剩余的元素
while(rightPos <= rightEnd)
tmp[tmpPos++] = v[rightPos++];
//拷貝回原數(shù)組
//for(int i = rightEnd; i >= start; --rightEnd){
for(int i = 0; i < numElement; ++i, --rightEnd){
v[rightEnd] = tmp[rightEnd];
}
}
//自底向上歸并排序?qū)崿F(xiàn)
static void MergeSortDownToUp(vector<int> &v, int len){
/* 拆分版：遍歷實(shí)現(xiàn)相鄰兩組的元素進(jìn)行歸并排序
for(int gap = 1; gap < len; gap *= 2){
mergeGroups(v, len, gap);
}
*/
/* 合并版 */
int i;
//遍歷實(shí)現(xiàn)相鄰兩組的元素進(jìn)行歸并排序
for(int gap = 1; gap < len; gap *= 2){
//相鄰的子數(shù)組歸并排序的主實(shí)現(xiàn)
for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
Merge(v, i, i + gap - 1, i + 2 * gap - 1);
}
//組數(shù)為奇數(shù)時，剩余一個組未配對
if(i + gap - 1 < len){
Merge(v, i, i + gap - 1, len - 1);
}
}
}
//分組合并排序?qū)崿F(xiàn)（將相鄰的子數(shù)組進(jìn)行合并排序）
static void mergeGroups(vector<int> &v, int len, int gap){
int i;
//相鄰的子數(shù)組歸并排序的主實(shí)現(xiàn)
for(i = 0; i + 2 * gap - 1 < len; i += (2 * gap) ){
Merge(v, i, i + gap - 1, i + 2 * gap - 1);
}
//組數(shù)為奇數(shù)時爬立，剩余一個組未配對
if(i + gap - 1 < len){
Merge(v, i, i + gap - 1, len - 1);
}
}
//堆排序
static void HeapSort(vector<int> &v){
int len = v.size();
//建立初始堆
for(int i = len / 2; i >= 0; --i){
percDown(v, i, len);
}
//deleteMax
for(int j = len - 1; j > 0; --j){
swap(v[0], v[j]);
percDown(v, 0, j);
}
}
//堆排序下濾實(shí)現(xiàn)
static void percDown(vector<int> &v, int iter, int len){
int child;
int tmp = v[iter]; //create hole
for( ; 2 * iter + 1 < len; iter = child){
child = 2 * iter + 1; //獲取該節(jié)點(diǎn)的左孩子下標(biāo)
//如有右孩子钾唬，且右孩子大于左孩子，下標(biāo)改成右孩子下標(biāo)
if(child != len - 1 && v[child] < v[child + 1] )
child++;
//孩子結(jié)點(diǎn)值大于該結(jié)點(diǎn)值侠驯，則下濾
if(tmp < v[child])
v[iter] = v[child];
else //否則抡秆，說明結(jié)點(diǎn)處于正確位置，可跳出循環(huán)
break;
}
v[iter] = tmp; //把hole堵上
}
//快速排序
static void QuickSort(vector<int> &v){
QuickSortRecursion(v, 0, v.size() - 1);
}
static void QuickSortRecursion(vector<int> &v, int left, int right){
/* 優(yōu)化做法 */
if(left + 5 <= right){
int pivot = getPivot(v, left, right);
int front = left;
int rear = right - 1;
//int front = left + 1;
//int rear = right - 2;
while(1){
while(v[++front] < pivot){ }
while(v[--rear] > pivot){ }
if(front < rear)
swap(v[front], v[rear]);
else
break;
}
swap(v[front], v[right - 1]);
QuickSortRecursion(v, left, front - 1); //sort small elements
QuickSortRecursion(v, front + 1, right); //sort large elements
}
else{
InsertSortForQSort(v, left, right);
}
/* 純快排做法
if(right - left <= 1){ //遞歸出口吟策，小于兩個元素情況的處理
if(v[left] > v[right])
swap(v[left],v[right]);
return;
}
int pivot = getPivot(v, left, right); //樞紐元
int front = left;
int rear = right - 1;
while(1){
//首尾指針向中間靠攏
while(v[++front] < pivot){ }
while(v[--rear] > pivot){ }
//front小于rear則交換元素
if(front < rear)
swap(v[front], v[rear]);
else
break; //front儒士、rear交錯，則不再交換檩坚，跳出循環(huán)
}
swap(v[front], v[right - 1]); //將樞紐元放到正確位置
QuickSortRecursion(v, left, front - 1); //sort small elements
QuickSortRecursion(v, front + 1, right); //sort large elements
*/
}
//三數(shù)中值取樞紐元
static int getPivot(vector<int> &v, int left, int right){
int mid = (left + right) / 2;
if(v[left] > v[mid])
swap(v[left], v[mid]);
if(v[left] > v[right])
swap(v[left],v[right]);
if(v[mid] > v[right])
swap(v[mid], v[right]);
swap(v[mid], v[right - 1]);
return v[right - 1];
}
private:
void (*CallSort)(vector<int> &v);
//適配快排的插入排序
static void InsertSortForQSort(vector<int> &v,int left, int right){
int tmp, i, j;
for(i = left + 1; i <= right; ++i){
tmp = v[i];
for(j = i; j >= left && tmp < v[j - 1]; --j)
v[j] = v[j - 1];
v[j] = tmp;
}
}
};
#endif
