010-排序算法

moc

1、基本概念
排序是计算机内存经常要进行的一种操作，其目的是将“无序”的数据元素调整为“有序”的数据元素。
排序的稳定性： 如果在序列中有两个元素 r[ i ] 和 r[ j ]，如果他们的关键字相等，在排序之前  r[ i ] 排在 r[ j ]前面，排序后如果仍在前面则该排序方法，否在该算法不稳定。
排序可以按一个关键字也可以按照多个关键字，多关键字排序与单关键字排序并无本质区别。
排序的时间性能是区分排序算法好坏的主要因素。
2、选择法
基本思想：  每一趟（如第 i 趟）在后面 n - i 个待排的数据元素中选出关键字最小的元素，作为有序元素序列的第 i 个元素。

void swap(int *buf, int i, int j)
{
        int temp = buf[i];
        buf[i] = buf[j];
        buf[j] = temp;
}

void selectionSort(int *array, int len)
{
        int i = 0, j = 0, k = -1;
        for (i = 0; i < len; i++)
        {
                k = i;  // 寻找最小元素的下标
                for (j = i + 1; j < len; j++)
                {
                        if (array[j] < array[k])
                        {
                                k = j;
                        }
                }
                swap(array, i, k);
        }
}

3、插入法
基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

void InertionSort(int *array, int len)
{
        int i = 0, j = 0, k = -1, temp = -1;
        for (i = 1; i < len; i++)
        {
                k = i;  // 待插入位置
                temp = array[k];

                for (j = i - 1; (j >= 0) && (array[j] > temp); j--)
                {
                        array[j + 1] = array[j];  // 元素后移
                        k = j;   //需要插入的位置
                }
                array[k] = temp;
        }
}

4、冒泡法
基本思想：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

（优化版）
void BubbleSort(int *array, int len)
{
        int i = 0, j = 0;
        int exchange = 1;  // 标记数组是否排序好  排序好记为0  未排序好记为1
        
        for (i = 0; (i < len) && exchange; i++)
        {
                exchange = 0;   // 认为已排序好
                for (j = len - 1; j > i; j--)
                {
                        if (array[j] < array[j - 1])
                        {
                                swap(array, j, j - 1);
                                exchange = 1;   // 如果上面执行过啦，说明未排序好
                        }
                }
        }
}

5、希尔排序
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

void ShellSort(int *array, int len)
{
        int i = 0, j = 0;
        int k = -1, temp = -1;
        int gap = len;

        do
        {
                // 业界统一实验的  平均最好情况  经过若干次后，收敛为1
                gap = gap / 3 + 1;    // O(1.3n)
                for (i = gap; i < len; i += gap)
                {
                        k = i;
                        temp = array[k];
                        
                        for (j = i - gap; (j >= 0) && (array[j] > temp); j -= gap)
                        {
                                array[j + gap] = array[j];
                                k = j;
                        }
                        array[k] = temp;
                }
        } while (gap > 1);
}

6、快速排序
基本思想： 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

// 划分过程  第一个元素当枢轴，分成2个有效子序列
int partition(int *array, int low, int high)
{
        int pv = array[low];
        while (low < high)
        {
                while ((low < high) && (array[high] >= pv))
                {
                        high--;   // 比基准大，本来就在右边，所以high前移
                }
                swap(array, low, high);
                while ((low < high) && (array[low] <= pv))
                {
                        low++;
                }
                swap(array, low, high);
        }
        // 返回枢轴的位置 ... **
        return low;
}

void QSort(int *array, int low, int high)
{
        if (low < high)
        {
                // 选一个pv值，把数据分别放在pv值的左右两边并把pv的位置pivot返回来
                int pivot = partition(array, low, high);

                // 对子序列1排序
                QSort(array, low, pivot - 1);
                // 对子序列2排序
                QSort(array, pivot + 1, high);
        }
}

void QuickSort(int *array, int len)
{
        QSort(array, 0, len - 1);
}

7、归并排序
基本思想： 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

//src中 low --> mid是一个排好的序列； mid+1 -->high 是另一个排好的序列。
void Merge(int *src, int *des, int low, int mid, int high)
{
        int i = low;
        int j = mid + 1;
        int k = low;

        while ((i <= mid) && (j <= high) ) // 将小的放入目的地des
        {
                if (src[i] < src[j])
                {
                        des[k++] = src[i++];
                }
                else
                {
                        des[k++] = src[j++];
                }
        }

        while (i <= mid)  // 若尾部有剩余的元素
        {
                des[k++] = src[i++];
        }
        while (j <= high)  // 若尾部有剩余的元素
        {
                des[k++] = src[j++];
        }
}

// 每次分两路 当只剩下一个元素时，就不需要再划分
void MSort(int *src, int *des, int low, int high, int max)
{
        if (low == high)  // 只有一个元素，不需要归并，结果赋给des[low]
        {
                des[low] = src[low];
        }
        else   // 如果多个元素进行两路划分
        {
                int mid = (low + high) / 2;
                int *space = (int*)malloc(sizeof(int)*max);
                
                // 递归进行两路， 两路划分
                // 当剩下一个元素的时，递归划分结束，然后开始merge归并操作
                if (space != NULL)
                {
                        MSort(src, space, low, mid, max);
                        MSort(src, space, mid + 1, high, max);
                        Merge(space, des, low, mid, high);  // 调用归并函数进行归并
                }
                free(space);
        }
}

void MergeSort(int *array, int len)
{
        MSort(array, array, 0, len - 1, len);
}

7、各种排序的比较

鱼油_hi

感谢楼主的收集！