排序算法

• 冒泡排序

void bubble_sort(int a[],int n)
{
    //要进行N-1轮比较
    bool is_sorted = true;
    for(int i = 0; i < n-1; i++ )//[0,n-2]恰好n-1轮比较
    {
                is_sorted = true;
        for(int j = 0; j < n-i-1 ; j++)//已经排好序的最后i个不用比较，要比较的数的个数为n-i个，那么需要比较的次数为n-i-1
        {
            if(a[j] > a[j+1]){
                is_sorted = false;
                swap(a[j],a[j+1]);
            }
        }
        if(is_sorted)//如果没有发生交换，说明已经排好序了，提前退出循环,所以最好情况下时间复杂度为O（N）
            break;
    }

• 快速排序

   public static void quickSort(int [] arr,int left,int right) {
      int pivot=0;
      if(left<right) {
         pivot=partition(arr,left,right);
         quickSort(arr,left,pivot-1);
         quickSort(arr,pivot+1,right);
      }
   }
   
      private static int partition(int[] arr,int left,int right) {
      int key=arr[left];
      while(left<right) {
         while(left<right && arr[right]>=key) {
            right--;
         }
         arr[left]=arr[right];
         while(left<right && arr[left]<=key) {
            left++;
         }
         arr[right]=arr[left];
      }
      arr[left]=key;
      return left;
   }

• 直接插入排序

/*
 * 直接插入排序
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     n -- 数组的长度
 */
void insert_sort(int a[], int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
        for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        //如找到了一个合适的位置
        if (j != i - 1)
        {
            //将比a[i]大的数据向后移
            int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

• 折半插入排序

public static void sort(int[] source) {
        int size = source.length;
        for (int i = 1; i < size; i++) {
            // 拿出来
            int temp = source[i];
            int begin = 0; // 标记排好序的数组的头部
            int end = i - 1; // 标记排好序数组的尾部
            // 只要头部一直小于尾部，说明temp还在2个标记范围内
            while (begin <= end) {
                // 取2个标记的中间数据的值
                int mid = (begin + end) / 2;
                // 比较，若比中间值大，则范围缩小一半
                if (temp > source[mid]) {
                    begin = mid + 1;
                    // 否则，范围也是缩小一半
                } else {
                    end = mid - 1;
                }
                // 循环结束时，end<begin,即i应该插入到begin所在的索引
            }
            // 从begin到i，集体后移
            for (int j = i; j > begin; j--) {
                source[j] = source[j - 1];
            }
            // 插入i
            source[begin] = temp;
            SortUtil.outputArray(source);
        }
    }

• 希尔排序

Shell Sort

typedef int ElemType;
void ShellSort(ElemType A[],int n)
{
    ElemType x;
    int i,j,d;
    for(d=n/2;d>=1;d/=2)
    {
        for(i=d;i<n;++i)
        {
            x=A[i];
            j=i-d;
            while(A[j]>x)
            {
                A[j+d]=A[j];
                j-=d;
            }
            A[j+d]=x;

        }
    }
}

• 简单选择排序

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

• 堆排序

public void HeapAdjust(int[] array, int parent, int length) {

    int temp = array[parent]; // temp保存当前父节点

    int child = 2 * parent + 1; // 先获得左孩子

 

    while (child < length) {

        // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点

        if (child + 1 < length && array[child] < array[child + 1]) {

            child++;

        }

 

        // 如果父结点的值已经大于孩子结点的值，则直接结束

        if (temp >= array[child])

            break;

 

        // 把孩子结点的值赋给父结点

        array[parent] = array[child];

 

        // 选取孩子结点的左孩子结点,继续向下筛选

        parent = child;

        child = 2 * child + 1;

    }

 

    array[parent] = temp;

}

 

public void heapSort(int[] list) {

    // 循环建立初始堆

    for (int i = list.length / 2; i >= 0; i--) {

        HeapAdjust(list, i, list.length);

    }

 

    // 进行n-1次循环，完成排序

    for (int i = list.length - 1; i > 0; i--) {

        // 最后一个元素和第一元素进行交换

        int temp = list[i];

        list[i] = list[0];

        list[0] = temp;

 

        // 筛选 R[0] 结点，得到i-1个结点的堆

        HeapAdjust(list, 0, i);

        System.out.format("第 %d 趟: \t", list.length - i);

        printPart(list, 0, list.length - 1);

    }

}

• 归并排序

//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
    int i, j, k;

    i = j = k = 0;
    while (i < n && j < m)
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++]; 
    }

    while (i < n)
        c[k++] = a[i++];

    while (j < m)
        c[k++] = b[j++];
}