Day.17——数据结构学习——9种经典排序算法、七种经典查找算法

布满荆棘的人生 2023-06-05 08:49 60阅读 0赞

国庆回来，一切ok，状态依旧，学习紧迫感愈发强烈，多事之秋，NBA被封啥的，我 不 关 心。。。

### 本文目录 ###

*  排序算法
 *   *  简单排序
     *   *  冒泡排序
         *  插入排序
         *  选择排序
     *  其它排序
     *   *  希尔排序
         *  堆排序
         *  归并排序
         *  快速排序
         *  表排序
         *  基数排序
 *  查找算法
 *   *   *  顺序查找
         *  二分查找
         *  插值查找
         *  斐波那契查找
         *  树表查找
         *   *  二叉树查找算法
             *  平衡查找树之2-3查找树
             *  平衡查找树之红黑树
             *  B树和B+树
         *  分块查找
         *  哈希查找

# 排序算法 #

void X_Sort( ElementType A[], int N )

> 写在前面，首先需要明白本次学习的目的，即对经典的排序算法思路及类别有基本的了解。于是针对此目的，我们开始吧。

我会倾向于将排序算法分为两大类：*简单排序*、*其他排序*

简单排序：排序时每交换一次元素，消除一个“逆序对”，总共需要交换的次数等于初始序列的逆序对总数量。

## 简单排序 ##

冒泡排序、插入排序

### 冒泡排序 ###

![在这里插入图片描述][aHR0cHM6Ly9naXRlZS5jb20vd2gxOTkweGlhbzIwMDUvd2gxOTkweGlhbzIwMDUvcmF3L21hc3Rlci9waG90b2dyYWdoLyVFNSU4NiU5MiVFNiVCMyVBMSVFNiU4RSU5MiVFNSVCQSU4RiVFNSU4NSVBOCVFOCVCRiU4NyVFNyVBOCU4Qi5naWY_400]  
伪码描述：

void Bubble_Sort( ElementType A[], int N )
    { 
        for( P = N-1; P>=0; P--)
        { 
           flag = 0;
           for( i = 0; i < P; i++ )
               { 
                  if( A[i] > A[i+1] )
                     { 
                        Swap ( A[i], A[i+1] );
                        flag = 1;
                     }
               }
          if(flag == 0) break;
        }
    }

一趟一趟，两两相邻的元素对比，进行排序。

### 插入排序 ###

类似于打扑克牌的时候，你摸牌时的排序操作  
![在这里插入图片描述][SouthEast]  
伪码描述

void Insertion_Sort( ElementType A[], int N )
    { 
         for (p = 1; p < N; p++)
              { 
                Tmp = A[P];
                for ( i = p; i > 0 && A[i-1]>Tmp; i-- )
                      A[i] = A[i-1];
                A[i] = Tmp;
              }
    }

由于简单排序每次交换元素只能消除一个逆序对，所以效率有点低，我们寻找其它算法解决这个问题

### 选择排序 ###

选择排序（Select Sort） 是直观的排序，通过确定一个 Key 最大或最小值，再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)

**算法描述**：

1.  在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
2.  第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
3.  重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

**算法可视化**：  
![在这里插入图片描述][20210330095519829.gif_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70]

## 其它排序 ##

希尔排序、堆排序、归并排序、快速排序、表排序、基数排序

### 希尔排序 ###

![在这里插入图片描述][format_png]

思路：交换两个相隔较远的元素，这样可以达到每次交换减少更多的逆序对  
步骤：①定义增量序列 Dn>Dn-1…>D1=1  
②对每个Dk进行“Dk间隔”排序 （k=M，M-1，…，1）

根据①中增量序列的不同可以将希尔排序分为：原始希尔排序、Hibbord增量序列、Sedgewick增量序列

### 堆排序 ###

主要思路是，先将原始序列构成堆，然后将该堆排为最大堆，接着依次将堆顶与堆顶做调换。  
详细图文见：https://blog.csdn.net/u010452388/article/details/81283998

//堆排序
        public static void heapSort(int[] arr) { 
            //构造大根堆
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) { 
                //固定最大值
                swap(arr, 0, size - 1);
                size--;
                //构造大根堆
                heapify(arr, 0, size);
            }
        }
     
        //构造大根堆（通过新插入的数上升）
        public static void heapInsert(int[] arr) { 
            for (int i = 0; i < arr.length; i++) { 
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
                //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
                while (arr[currentIndex] > arr[fatherIndex]) { 
                    //交换当前结点与父结点的值
                    swap(arr, currentIndex, fatherIndex);
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        
        //将剩余的数构造成大根堆（通过顶端的数下降）
        public static void heapify(int[] arr, int index, int size) { 
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size) { 
                int largestIndex;
                //判断孩子中较大的值的索引（要确保右孩子在size范围之内）
                if (arr[left] < arr[right] && right < size) { 
                    largestIndex = right;
                } else { 
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值，并确定最大值的索引
                if (arr[index] > arr[largestIndex]) { 
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
                if (index == largestIndex) { 
                    break;
                }
                //父结点不是最大值，与孩子中较大的值交换
                swap(arr, largestIndex, index);
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
        }
        
        //交换数组中两个元素的值
        public static void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

### 归并排序 ###

思想：将原始序列分为两段，然后将该两段排序  
类别：递归算法、非递归算法

![在这里插入图片描述][format_png_pic_center]

class Solution { 
        vector<int> tmp; //用来临时存储数组
        
        void mergeSort(vector<int>& nums, int L, int R) { 
            if (L >= R) return;
            
            int mid = (L + R) >> 1;   //mid = (L+R)/2
            mergeSort(nums, L, mid);
            mergeSort(nums, mid + 1, R);
            
            int i = L, j = mid + 1;
            int cnt = 0;
            while (i <= mid && j <= R) { 
                if (nums[i] < nums[j]) { 
                    tmp[cnt++] = nums[i++];
                }
                else { 
                    tmp[cnt++] = nums[j++];
                }
            }
            while (i <= mid) tmp[cnt++] = nums[i++];
            while (j <= R) tmp[cnt++] = nums[j++];
            for (int i = 0; i < R - L + 1; ++i) nums[i + L] = tmp[i];
        }
        
    public:
        vector<int> sortArray(vector<int>& nums) { 
            tmp.resize((int)nums.size(), 0);   //用来临时存储数组
            mergeSort(nums, 0, (int)nums.size() - 1);
            return nums;
        }
    };

### 快速排序 ###

思想：也是分而治之的思想  
步骤：先选出一个主元，然后将原始序列分为两拨，一拨比主元小，另一拨比主元大。  
**①单向前进型**  
![在这里插入图片描述][aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL3NvbHV0aW9uLXN0YXRpYy85MTJfZmlnMS5naWY]  
pivot为主元，i 和 j 都是朝着右边前进，当j遇到比主元小的数时，i前进一格，并将前进一格后所在位置的元素与 j 此时所在位置的元素进行交换，即达到左边的元素都是比主元小的。

int partition(vector<int>& nums, int l, int r) { 
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) { 
            if (nums[j] <= pivot) { 
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
        
    int randomized_partition(vector<int>& nums, int l, int r) { 
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
        
    void randomized_quicksort(vector<int>& nums, int l, int r) { 
        if (l < r){ 
            int pos = randomized_partition(nums, l, r);     //进行一次划分，并返回 划分后将主元放在pos = i+1 的位置
            randomized_quicksort(nums, l, pos - 1);         //左子列
            randomized_quicksort(nums, pos + 1, r);         //右子列
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {         //主程序
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }

#include <iostream>
    #include <vector>
    #include <time.h>
    using namespace std;
    inline int randomProc(vector<int>&, int, int);
    inline void quickSort(vector<int>&, int, int);
    int main(){ 
        unsigned seed;  // Random generator seed
        // Use the time function to get a "seed” value for srand
        seed = time(0);
        srand(seed);
        vector<int> vec;
        int a;
        while(cin>>a){ 
            vec.push_back(a);
            if(cin.get() == '\n') break;
        }
        quickSort(vec, 0, vec.size()-1);
        for(auto k : vec){ 
            cout<<k<<" ";
        }
        cin.get();
        return 0;
    }
    
    inline void quickSort(vector<int>& vec, int l, int r){ 
        if(l<r){ 
            int pLoc = randomProc(vec, l, r); //对l,r之间进行第一次分裂,并返回参考值坐标
            quickSort(vec, l, pLoc-1);
            quickSort(vec, pLoc+1, r);
        }
    }
    
    inline int randomProc(vector<int>& vec, int l, int r){ 
        int p = l + rand()%(r-l);
        swap(vec[r], vec[p]);
        int pval = vec[r];
        int i = l-1;
        for(int j=l; j<r; j++){ 
            if(vec[j] < pval){ 
                i++;
                swap(vec[i], vec[j]);
            }
        }
        swap(vec[i+1], vec[r]);
        return i+1;
    }

**②双向前进型**  
![在这里插入图片描述][20190120162905962.gif_pic_center]  
图中的P就是主元

int sub_quick_sort(vector<int>& nums,int L, int R)  
    { 
        int i = L;
        int j = R-1;
        int pivot = nums[R];
        while (true)
    		{ 
    			while (i <= j && nums[i] <= pivot) i++;
    			while (i <= j && nums[j] >= pivot) j--;
    			if (i > j) break;
    			swap(nums[i], nums[j]);
    		}
        swap(nums[i], nums[R]);
        return i; //主元放在了nums[i]上
    }
    
    int find_pivot(vector<int>& nums, int L, int R)  //随机确定主元，并放在数组的右边nums[R]
    { 
        int tmp = L + rand()%(R - L +1) ;
        swap(nums[tmp],nums[R]);
        return sub_quick_sort(nums, L, R);
    }
    
    vector<int> quick_sort(vector<int>& nums, int L, int R)    //快速排序！！！，对nums序列L~R段进行排序
    { 
        if(L<R)
        { 
        int pivot = find_pivot(nums, L, R);
        quick_sort(nums, L, pivot-1);
        quick_sort(nums, pivot+1, R);
        }
        return nums;
    }

### 表排序 ###

思想：要想明白其思想，想要看它的应用场景，其实就是，当元素过大时，比如是一个结构体、一部电影、一本书，不能直接对元素进行排序，于是我们定义一个指针数组作为“表”，用排序算法对指针数组进行排序

### 基数排序 ###

![在这里插入图片描述][20190219112853647.png]  
思想：桶排序

# 查找算法 #

点击参考博客[https://www.cnblogs.com/maybe2030/p/4715035.html][https_www.cnblogs.com_maybe2030_p_4715035.html]

### 顺序查找 ###

### 二分查找 ###

### 插值查找 ###

### 斐波那契查找 ###

### 树表查找 ###

#### 二叉树查找算法 ####

#### 平衡查找树之2-3查找树 ####

#### 平衡查找树之红黑树 ####

#### B树和B+树 ####

### 分块查找 ###

### 哈希查找 ###

*注：本篇博客中部分图片来源于网络，侵删*

[aHR0cHM6Ly9naXRlZS5jb20vd2gxOTkweGlhbzIwMDUvd2gxOTkweGlhbzIwMDUvcmF3L21hc3Rlci9waG90b2dyYWdoLyVFNSU4NiU5MiVFNiVCMyVBMSVFNiU4RSU5MiVFNSVCQSU4RiVFNSU4NSVBOCVFOCVCRiU4NyVFNyVBOCU4Qi5naWY_400]: /images/20230601/728b64ccf26946c2958339fe4ea8591d.png
[SouthEast]: /images/20230601/c076fa811750459cbd0694080f252dde.png
[20210330095519829.gif_pic_center]: /images/20230601/88833015414a4f48b8ea00a9e22ab64e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDc3MDEyNw_size_16_color_FFFFFF_t_70]: /images/20230601/af5537100d9b4c2ba4fd03b06ede5bac.png
[format_png]: /images/20230601/dc7caf860feb440498494619fe0880b6.png
[format_png_pic_center]: /images/20230601/06ec27a5ce5e4fa08468668fb14e99ef.png
[aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL3NvbHV0aW9uLXN0YXRpYy85MTJfZmlnMS5naWY]: /images/20230601/2249dd39cfb34ed9822256635b0edb37.png
[20190120162905962.gif_pic_center]: /images/20230601/023a150f75654dd5abeab755a3951ab9.png
[20190219112853647.png]: /images/20230601/77a84a7c0a8843b1943eb0ea75aedbe9.png
[https_www.cnblogs.com_maybe2030_p_4715035.html]: https://www.cnblogs.com/maybe2030/p/4715035.html