数据结构：查找与排序

注：以下代码均为C++

查找

一、线性表的查找

1. 顺序查找

int search_seq(vector<int> s, int key){
    for(int i = 0; i < s.size(); i++){
        if(s[i] == key)
            return i;
    }
    return -1;
}

2. 折半查找

(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. 二叉排序树的查找

(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);
}

排序

一、插入排序（从小到大排序）

1. 直接插入排序

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;  //插入元素
        }
    }
}

2. 折半插入排序

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;
    }
}

3. 希尔排序：缩小增量的多遍插入排序，每个子表是直接插入排序

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]);
}

二、交换排序

1. 冒泡排序

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;
            }
        }
    }
}

2. 快速排序

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);
    }
}

三、选择排序

1. 简单选择排序：每次从待排序的序列中选择最小的数，存放在待排序序列的起始位置

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;
        }
    }

}