数据结构---排序算法总结

比眉伴天荒 2022-07-15 10:22 204阅读 0赞

## 一、插入排序 ##

### 1、直接插入排序 ###

### 2、折半插入排序 ###

### 3、希尔排序 ###

--------------------

#### 1.1直接插入排序 ####

是最简单直接的排序方法。它的基本思想是将新的关健值插入到排好序的前序记录中，所要做的就是找到该关键值应该处的位置（关于找位置可以用折半查找法提高效率，下面介绍）。

具体做法：原始数组长度为N的序列，插入索引为i(i <Ｎ)的关健值。前提是前面i个关健值a\[0\].a\[1\],a\[2\]…a\[i-1\]已经排好序，找到a\[i\]应所处的位置将其插入，原来位置上的元素则往后移动。

void InsertSort(int a[],int len)
    {
        for(int i =1,i<len;i++)
        {
            int index = i;
            while(a[index] < a[index-1] && index > 0)
            {
                swap(a[index],a[index-1]);
                index--;
            }
        }
        for(int i = 0; i< len; i++)
            {
                cout<<setw(3)<<a[i];
            }
    }

--------------------

### 1.2折半插入排序 ###

折半插入和直接插入思想一致，只是在查找a\[i\]应该插入位置时，用折半查找法减少了比较次数。直接上代码：

void ZBInsertSort(int a[], int len)
    {
        for (int i = 1; i < len; i++)
        {
            int low, high, mid;
            low = 0;
            high = i;       
            while (low < high)
            {
                mid = (low + high) / 2;
                if (a[high] < a[mid])
                {
                    int temp = a[high];
                    for (int k = high ; k > mid; k--)
                    {
                        a[k] = a[k-1];
                    }
                    a[mid] = temp;
                    high = mid;
                }
                else
                    low = mid + 1;
            }   
    
            for (int k = 0; k <len; k++)
                cout << setw(3)<< a[k];
        }
    }

--------------------

### 1.3希尔排序 ###

又名“缩小增量排序法“，它的主要思想是不断把待排序的一组记录按照间隔值分成若干小组，对每一组采用直接插入排序。

void ShellSort(int a[],int len)
    {
        for (int gap = len / 2; gap >= 1; gap /= 2)
        {
            for (int i = gap; i < len; i++)
            {
                if (a[i] < a[i - gap])
                {
                    swap(a[i],a[i-gap]);
                }
            }
            for (int i = 0; i < len; i++)
                cout << setw(3) << a[i];
        }
    }

继续更新。。。

## 二、交换排序 ##

### 2.1、冒泡排序 ###

### 2.2、快速排序 ###

--------------------

#### 2.1冒泡排序 ####

冒泡排序很简单，将待排序数组看成是垂直树立的，将较大值或较小值从底部不断“涌”上来，与索引为“0,1，。。。N”的记录交换。记将“气泡”不断涌出“水面”。

void BubbleSort(int a[],int size)
    {
    
        for (int i = 0; i < size - 1; i++)
        {
            for (int j = size -1;j >= i;j--)
            {
                if (a[i] > a[j])
                    swap(a[i],a[j]);
    
            }
            cout << endl;
        for (int k = 0; k < size; k++)
            cout << setw(3) << a[k];
    
        }
    }

#### 2.2快速排序 ####

快速排序是基于冒泡改进而得。基本思想是：在待排序数组中随机选择一个记录（当然可以是第一个），将该记录放入关键位置。以升序排序为例，将该记录放入关键位置后，把所有小于该记录的放到该记录前面，大的放到该记录后面。因此该记录将会被分成2段“记录”，之后对两段数组采取同样的策略（递归）。快速排序如其名称一样，以快速为特点，时间复杂度低，也是常用几种排序方法之一，因此要重点掌握。

int QuickSort1(int s[], int low, int high)
    {
        int temp = s[low];//取第一个记录为基准记录
        int i = low, j = high;
        while (i < j)
        {
            while (i < j && s[j] >= temp)
                j--;//从后往前找到小于基准记录的索引
            if (i < j)
            {
                s[i++] = s[j];//将该索引上的记录赋值给原基准记录位置
            }
            while (i < j && s[i] < temp)//从前往后找大于基准记录的索引
                i++;
            if (i < j)
            {
                s[j--] = s[i];//同上
            }
        }
        s[i] = temp;//该基准记录最终位置
        return i;//返回“两段”中间的索引方便递归
    }
    void QuickSort2(int s[], int low, int high)
    {
        if (low < high)
        {
            int pos = QuickSort1(s, low, high);
            QuickSort2(s,low,pos - 1);
            QuickSort2(s,pos + 1,high);
        }
    }

## 三、选择排序 ##

### 3.1、直接选择排序 ###

### 3.2、堆排序 ###

--------------------

#### 3.1直接选择排序 ####

这是一种简单的排序方式，速度较慢。其思想是： 将整个待排序数组分成有序区和无序区，有序区位于左端，无序区位于右端。以正序排序为例，将最小值找出放在最左端，以此类推。。。  
（貌似与冒泡排序有点类似，注意它们细微的区别，虽然都是复杂度有点高的算法）

void SelectSort(int s[],int len)
    {
        for (int i = 0; i < len - 1; i++)
        {
            int pos = i,temp = s[pos];
            for (int j = i + 1; j < len; j++)
            {
                if (temp > s[j])
                {
                    pos = j;
                    temp = s[pos];
                }
            }
            s[pos] = s[i];
            s[i] = temp;
        }
    }

#### 3.2堆排序 ####

堆排序的意义在于，利用堆的结构来减少了重复比较的次数，使得速度提升。当然构建堆的过程也是time consuming的过程。不论是正序还是逆序，堆排序都是从数组尾部开始构建。因为堆排序总是需要用最上层的父节点和最后的子节点交换来排序。

void ArrayAdjust(int a[], int k, int size)
    {
        int ChildL = k * 2 + 1;
        int ChildR = k * 2 + 2;
        int temp = k;
        if (ChildL <= (size - 1) && a[temp] < a[ChildL])//之所以要这样是因为不确定节点数是奇数还是偶数，即最后一个父节点是有几个子节点。
            temp = ChildL;
        if (ChildR <= (size - 1) && a[temp] < a[ChildR])
            temp = ChildR;
        if (temp != k)//上层节点发生交换必然引起下层节点不符合堆的结构，因此要重新调整。
        {
            swap(a[temp],a[k]);
            ArrayAdjust(a,temp,size);//
        }
    
    }
    void BuildHeap(int a[],int size)//将[a[k]...a[size]]置为大根堆
    {
        for (int k = (size - 1) / 2; k >= 0; k--)//从最下面的子节点开始构建堆
            ArrayAdjust(a,k,size);
    
    }

## 三、归并排序 ##

所谓“归并”，就是把多个有序表合成新的有序表。文字说明不如code,好吧。

void Merge(int s[], int low,int high)
    {
        int mid = (low + high) / 2;
        int temp[len] = { 0 },k = 0;
        int i = low, j = mid + 1;
        while (i <= mid && j <= high)
        {
            if (s[i] < s[j])//正序
                temp[k++] = s[i++];
            else
                temp[k++] = s[j++];
        }
        while (i <= mid)
        {
            temp[k++] = s[i++];
        }
        while (j <= high)
        {
            temp[k++] = s[j++];
        }
        for (k = 0, i = low; i <= high; k++, i++)
            s[i] = temp[k];
    
    }
    void MergeSort(int s[],int low,int high)
    {
        int mid;
        if (low < high)
        {
            mid = (low + high) / 2;
            MergeSort(s,low,mid);//递归的调用将真个数组分成最小的长度为2的数组
            MergeSort(s, mid + 1, high);
            Merge(s, low, high);
            cout << endl;
            for (int i = 0; i < len; i++)
                cout << setw(3) << s[i];
        }
    }

持续更新。。。