赞
踩
注:以下代码均为C++
int search_seq(vector<int> s, int key){
for(int i = 0; i < s.size(); i++){
if(s[i] == key)
return i;
}
return -1;
}
(1)非递归:循环
int search_bin1(vector<int> s, int key){
int low = 0, high = s.size()-1, mid;
while(low <= high){
mid = (low + high) / 2;
if(key == s[mid])
return mid;
else if(key < s[mid])
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
(2)递归
int search_bin2(vector<int> s, int key, int low, int high){
if(low > high) return -1;
int mid = (low + high)/2;
if(key == s[mid])
return mid;
else if(key < s[mid])
return search_bin2(s, key, low, mid-1);
else
return search_bin2(s, key, mid+1, high);
}
int search_bin(vector<int> s, int key){
int ans = search_bin2(s, key, 0, s.size()-1);
return ans;
}
struct BSTree{
int data;
struct BSTree* lchild, *rchild;
};
(1)非递归:循环
BSTree* searchBST1(BSTree* T, int key){
if(T == NULL) return NULL;
while(T != NULL){
if(key == T->data)
return T;
else if(key < T->data)
T = T->lchild;
else
T = T->rchild;
}
}
(2)递归
BSTree* searchBST2(BSTree* T, int key){
if(T == NULL) return NULL;
if(key == T->data)
return T;
else if(key < T->data)
return searchBST2(T->lchild, key);
else
return searchBST2(T->rchild, key);
}
void insertSort(vector<int>& s){
if(s.size() <= 1) return;
for(int i = 1; i < s.size(); i++){
if(s[i] < s[i-1]){ //待插入的元素为s[i],若待插入元素比已排好序列的最后一位小,则开始插入排序,否则不用动它。
int temp = s[i]; //暂存单元
int j;
for(j = i-1; j >=0 && temp < s[j]; j--){ //找到插入位置
s[j+1] = s[j];
}
s[j+1] = temp; //插入元素
}
}
}
void BinsertSort(vector<int>& s){ if(s.size() <= 1) return; int i, j, low, high, mid; for(i = 1; i < s.size(); i++){ int temp = s[i]; //暂存单元 //查找插入位置 low = 0, high = i-1; while(low <= high){ mid = (low + high)/2; if(temp < s[mid]){ high = mid - 1; } else low = mid + 1; } //移动元素 for(j = i-1; j >= high+1; j--) s[j+1] = s[j]; //插入正确位置 s[high+1] = temp; } }
void shellInsert(vector<int>& s, int dk){ if(s.size() <= 1) return; for(int i = dk; i < s.size(); i++){ if(s[i] < s[i-dk]){ //待插入的元素为s[i],若待插入元素比已排好序列的最后一位小,则开始插入排序,否则不用动它。 int temp = s[i]; //暂存单元 int j; for(j = i - dk; j >= 0 && temp < s[j]; j = j - dk){ //找到插入位置 s[j+dk] = s[j]; } s[j+dk] = temp; //插入元素 } } } void shellSort(vector<int>& s, vector<int> dlta){ //dlta为增量数组 for(int i = 0; i < dlta.size(); i++) shellInsert(s, dlta[i]); }
void bubbleSort(vector<int>& s){ for(int i = 0; i < s.size() - 1; i++){ //n-1趟排序 for(int j = 0; j < s.size() - i; j++){ //每趟排序比较n-i次 if(s[i] > s[i+1]){ int temp = s[i]; s[i] = s[i+1]; s[i+1] = temp; } } } } //改进的冒泡排序:一旦某一趟比较时不出现记录交换,说明已经排好序了,可以直接结束算法,不需要再进行后续比较。 void bubbleSort1(vector<int>& s){ int flag = 1; for(int i = 0; i < s.size() - 1 && flag == 1; i++){ //n-1趟排序 flag = 0; for(int j = 0; j < s.size() - i; j++){ //每趟排序比较n-i次 if(s[i] > s[i+1]){ flag = 1; int temp = s[i]; s[i] = s[i+1]; s[i+1] = temp; } } } }
int partition(vector<int>& s, int low, int high){ int temp = s[low]; while(low < high){ while(low < high && s[low] < temp) low++; s[low] = s[high]; while(low < high && s[high] > temp) high--; s[high] = s[low]; } s[low] = temp; return low; } void Qsort(vector<int>& s, int low, int high){ if(low < high){ int loc = partition(s, low, high); Qsort(s, low, loc-1); Qsort(s, loc+1, high); } }
void selectSort(vector<int>& s){
for(int i = 0; i < s.size()-1; i++){
int min = i;
for(int j = i+1; j < s.size(); j++){
if(s[j] < s[min])
min = j;
}
if(min != i){
int temp = s[i];
s[i] = s[min];
s[min] = temp;
}
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。