排序

1.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ 插入排序）。

插入排序基本思想：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

插入排序的代码实现：

void StraightSort(int *arr,int len){
    int tmp; // 用于暂存当前元素的值
    int i; // 外层循环计数器
    int j; // 内层循环计数器

    for (i = 1; i < len; i++){ // 遍历数组，从第二个元素开始
        tmp = arr[i]; // 将当前元素的值暂存到tmp变量中
        for (j = i - 1; j >= 0 && arr[j] > tmp; j--){ // 内层循环用于将当前元素插入到已排序的序列中的正确位置
            arr[j + 1] = arr[j]; // 如果前一个元素比当前元素大，则将前一个元素后移一位
        }
        arr[j + 1] = tmp; // 将当前元素插入到正确位置
    }
}

希尔排序（shell排序）基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。

希尔排序需要定义一个增量，这里选择增量为gap=length/2，缩小增量以gap=gap/2的方式，这个增量可以用一个序列来表示，{n/2,(n/2)/2....1}，称为增量序列，这个增量是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

希尔排序代码如下：

// Shell排序算法，对数组arr进行排序，数组长度为len
void ShellSort(int *arr, int len) {
    // 使用希尔增量进行分组
    for (int gap = len/2; gap > 0; gap = gap/2) {
        // 对每个分组进行插入排序
        for (int i = gap; i < len; i++) {
            int j = i;
            // 插入排序
            while (j - gap >= 0 && arr[j] < arr[j - gap]) {
                Swap(arr, j, j - gap); // 调用Swap函数交换元素
                j = j - gap;
            }
        }
    }
}

归并排序基本思想：归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

 

冒泡排序的基本思想就是：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。

算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。

冒泡排序的代码：

void bubble_sort(int arr[], int len) {
    int i, j;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

选择排序的思想：利用线性查找搜索出待排序列中的最小元素，并将它移动到最前面，每完成一次遍历，都会使一个元素在正确位置，即第i趟排序后，前面i个元素在正确位置。

选择排序的代码：

// 选择排序
    // 每次找到一个最小的 放在正确的位置
    public void selectsort(int[] a) {
        int k = 0;
        int temp = 0;
        for (int i = 0; i < a.length - 1; i++) {//i控制每趟循环，从第一个元素开始
            k = i;//第i趟，k取出第i个数据与后边的数据进行比较（假设k此时为最小元素）
            for (int j = i; j < a.length; j++) {//内层循环用于找出最小元素
                if (a[j] < a[k]) {
                    k = j;//k用来记录最小元素的下标

                }
            }

            temp = a[i];
            a[i] = a[k];
            a[k] = temp;//将最小数据与待排序列的第一个元素交换

        }
        for (int num : a) {
            System.out.print(num + " ");
        }
    }

快速排序属于分治算法，分治算法都有三步：分成子问题  递归处理子问题  子问题合并

快速排序的代码：

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}