大师兄的数据结构学习笔记(十五）: 串

一、关于排序

• 将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。
  
• 首先分为内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
• 其次，根据是否需要对数据关键字进行比较，分为比较排序和非比较排序。
• 如果在每一次单趟排序后，相同关键字的相对顺序不变，称为稳定排序。例：冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。

二、直接插入排序

• 直接插入排序是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
• 在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

• 在数组A=（5,2,4,6,1,3）上插入排序的操作。
• 对数组运行for循环的迭代。
• 每次迭代中，黑色的长方形保存取自A[j]的关键字，在第5行的测试中将它与其左边的加阴影的长方形中的值进行比较。
• 加阴影的箭头指出数组值在第6行向右移动一个位置，黑色的箭头指出在第8行关键字被移到的地方。
• (f)最终排序好的数组 。

• 插入排序的最好情况:顺序,最坏情况:逆序。

template<typename ElementType>
void Insertion_sort(ElementType A[], int N)
{   
    int i = 0;
    for (int P = 1; P < N; P++)
    {
        int key = A[P];
        for (i = P-1; i >= 0; i--)
        {
            if (A[i] <= key)
            {
                A[i + 1] = key;
                break;
            }
            A[i + 1] = A[i];
        }
        if (i < 0)A[0] = key;
    }
}

三、希尔排序

• 由于插入排序有以下两个特点：

1) 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
2) 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

• 基于以上特点，希尔排序(Shell Sort)对插入排序进行了改进:

1) 首先将待排序列按固定间隔d分为若干个组。
2) 对这些分组分别进行直接插入排序。
3) 重复1和2若干次，每次间隔减半。
4) 经过以上操作，整个序列的有序度一定会被提高，逆序对一定会变少。
5) 最后，再对整个序列进行一趟直接插入排序。

• 平均时间复杂度为左右。

template<typename ElementType>
void Shell_sort(ElementType A[], int N)
{
    int gap = N;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = gap; i < N; i++)
        {
            int key = A[i];
            int start = i - gap;
            while (start >= 0 && key <= A[start])
            {
                A[start + gap] = A[start];
                start -= gap;
            }
            A[start + gap] = key;
        }
    }
}

四、简单排序

• 简单排序非常简单，就是遍历N次数组，每次从当前待排序列中选出最小的放在已拍好序列的末尾。
  
• 平均时间复杂度:

template<typename ElementType>
void Select_sort(ElementType A[], int N)
{
    int begin = 0;
    int end = N - 1;
    int max = 0;
    int min = 0;
    for (int i=0;i<N-1;i++)
    {
        max = begin;
        min = begin;
        for (int i = begin; i <= end; i++)
        {
            if (A[i] >= A[max])
            {
                max = i;
            }
            if (A[i] < A[min])
            {
                min = i;
            }
        }
        if (max == begin && min == end)
        {
            swap(A[max], A[end]);
            continue;
        }
        if (max == begin)
        {
            swap(A[max], A[end]);
            swap(A[min], A[begin]);
            continue;
        }
        if (min == end)
        {
            swap(A[min], A[begin]);
            swap(A[max], A[end]);
            continue;
        }
        swap(A[min], A[begin]);
        swap(A[max], A[end]);
        begin++;
        end--;
    }
}

五、堆排序

• 详见大师兄的数据结构学习笔记(七）:堆。

六、冒泡排序

• 冒泡排序是一种交换排序，保证右边的元素始终大于左边的元素。
• 具体做法是将序列当中的元素依次两两比较，如果左侧大于右侧，则交换元素位置，直到没有反序的记录为准。
• 时间复杂度为。
  

void Bubble_Sort(ElementType A[], int N)
{
    int end = N - 1;
    while (end > 0)
    {
        bool exchange = false;
        for (int i = 0; i < end; i++)
        {
            if (A[i] > A[i + 1])
            {
                swap(A[i], A[i + 1]);
                exchange = true;
            }
        }
        if (!exchange)
        {
            return;
        }
        else
        {
            exchange = false;
        }
        end--;
    }
}

七、快速排序

• 快速排序基于冒泡排序进行了改进，因为速度快成为最常用的排序算法之。
• 快速排序基本分治法的思想:

1) 在数组中任取一个元素pivot作为基准，并预设L、R两个下标指针。

2) 移动R下标向左，比较当前数字与pivot比较，如果小于pivot则放在左侧，反之放在右侧

3a) 如果上一次的元素有操作移动位置，则交替移动L下标向右比较，否则继续移动R向左。

3b) 就这样交替移动，直到两个下标重合，就是pivot的位置，这样就完成第一次排序。

4) 第一次排序后，获得两个子序列，pivot左侧元素全部小于pivot，右侧全部大于等于pivot。

5a) 对左右两个子序列递归重复1、2、3的操作。

5b) 如果序列长度为一，则认为是顺序序列。

6) 最终获得顺序数组

• 基于指针数，可以分为单路快速排序，双路快速排序，三路快速排序。
• 时间复杂度为。

template<typename ElementType>
void Quick_Sort(ElementType A[], int low,int high)
{
    if (low >= high)return;
    int i, j, temp;
    i = low, j = high;
    int pivot = A[low]; //选择最左边的元素为pivot
    while (i < j)
    {
        while (A[j] >= pivot && i < j)
            j--;
        while (A[i] <= pivot && i < j)
            i++;
        if (i < j)
        {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }

    A[low] = A[i];
    A[i] = pivot;
    Quick_Sort(A,low,i-1);
    Quick_Sort(A, i + 1, high);
}

八、归并排序

• 归并排序是建立在归并操作上的排序算法。
• 与快速排序类似归并排序也采用了分治法。
• 基本操作是：

1) 将序列每次折半拆分，即分解。
2) 将划分后的序列段两两排序合并，即合并。
3) 重复2)直到只剩下一组。

• 时间复杂度为。

template<typename ElementType>
//合并
void Merge(int A[], int low, int high, int mid)
{
    int n = high - low + 1;
    ElementType* temp = new ElementType[n];
    int i = 0;
    int left = low;
    int right = mid + 1;
    while (left <= mid && right <= high)
    {
        temp[i++] = A[left] <= A[right] ? A[left++] : A[right++];
    }
    while (left <= mid)
    {
        temp[i++] = A[left++];
    }
    while (right <= high)
    {
        temp[i++] = A[right++];
    }
    for (int j = 0; j < n; ++j)
    {
        A[low + j] = temp[j];
    }
    delete[] temp;
}

template<typename ElementType>
//分解
void Merge_Sort(ElementType A[], int low, int high)
{
    if (low == high)return;
    int mid = (low + high) / 2;
    Merge_Sort<ElementType>(A, low, mid);
    Merge_Sort<ElementType>(A, mid + 1, high);
    Merge<ElementType>(A, low, high, mid);
}

九、基数排序

• 基数排序通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

1) 分配：将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中。

2) 收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]。

3) 对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位。

• 时间复杂度为。

template<typename ElementType>
//计算最大位数
int maxbit(ElementType A[], int N)
{
    int d = 1;
    int p = 10;
    for (int i = 0; i < N; i++)
    {
        while (A[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}


template<typename ElementType>
void Radix_Sort(ElementType A[], int N)
{
    int d = maxbit<ElementType>(A, N);
    ElementType* temp = new ElementType[N];
    int count[10];
    int k;
    int radix = 1;
    for (int i = 1; i <= d; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            count[j] = 0; //清空计数器
        }
        for (int j = 0; j < N; j++)
        {
            k = (A[j] / radix) % 10; //每个桶中的记录数
            count[k]++;
        }
        for (int j = 1; j < 10; j++)
        {
            count[j] = count[j - 1] + count[j];
        }
        for (int j = N - 1; j >= 0; j--)
        {
            k = (A[j] / radix) % 10;
            temp[count[k] - 1] = A[j];
            count[k]--;
        }
        for (int j = 0; j < N; j++)
        {
            A[j] = temp[j];
        }
        radix *= 10;

    }
    delete[] temp;
}