(-)排序八大基本算法Java版

许多人都说算法是程序的核心,算法的好坏决定了程序的质量。作为一个初级phper,虽然很少接触到算法方面的东西。但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具。这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路。

基本算法分类结构

图片 1

基本排序算法.png

1. 插入排序

=====================================================

算法思想简单描述:

在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)–[n的平方]

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
1.从第一个元素开始,该元素可以认为已经被排序
2.取出下一个元素,在已经排序的元素序列中从后向前扫描
3.如果该元素(已排序)大于新元素,将该元素移到下一位置
4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

使用插入排序为一列数字进行排序的过程

图片 2

插入排序图解.gif

最差时间复杂度 O(n^2)
最优时间复杂度 O(n)

前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序。
$arr(1,43,54,62,21,66,32,78,36,76,39);

参考链接

http://www.cnblogs.com/0201zcr/p/4764427.html
http://www.cnblogs.com/qqzy168/archive/2013/08/03/3219201.html

平均时间复杂度O(n^2)

实例1:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace InsertionSorter
{
    public class InsertionSorter
{
        public void Sort(int[] list)
{
            //从第二个元素开始遍历
            for (int i = 1; i < list.Length;++i )
{
                //将第i个元素赋值给一个临时变量
                int t = list[i];
                //记录第i个元素的下标
                int j = i;
                //比较若list[j-1]>list[j],小标j -1; 并执行交换。 
                while ((j > 0) && (list[j - 1] > t))
{
                list[j] = list[j - 1];
                --j;
}
                //不管list[j-1]>list[j],或list[j-1]<=list[j],都执行下面语句;
                list[j] = t;
}
}
}
    class Program
{
        static void Main(string[] args)
{
            int[] iArray = new int[] { 1,5,3,6,10,55};
            InsertionSorter ii = new InsertionSorter();
                ii.Sort(iArray);
            for (int m = 0; m <= iArray.Length-1; m++)
                Console.WriteLine("{0}",iArray[m]);
            Console.ReadLine();            
}
}
}

1. 冒泡排序

思路分析:在要排序的一组数中,对当前还未排好的序列,从前往后对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即,每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

$arr=array(1,43,54,62,21,66,32,78,36,76,39);  
function bubbleSort($arr)
{  
  $len=count($arr);
  //该层循环控制 需要冒泡的轮数
  for($i=1;$i<$len;$i++)
  { //该层循环用来控制每轮 冒出一个数 需要比较的次数
    for($k=0;$k<$len-$i;$k++)
    {
       if($arr[$k]>$arr[$k+1])
        {
            $tmp=$arr[$k+1];
            $arr[$k+1]=$arr[$k];
            $arr[$k]=$tmp;
        }
    }
  }
  return $arr;
}

交换排序—冒泡排序

描述:
在排序数组Arrys中,对当前还未排好顺序的全部输,自上而下对相邻两数进行比较和调整。让较大的数往下沉,较小往下沉。即:发现相邻比较数顺序不符合排序要求,交换位置。
步骤:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
1.遍历数组起始位i,i到arrys.length-1
2.再次遍历数组,j位置到arrys.length-1-i
3.条件判断,交换位置操作

     /**
     * 冒泡升序
     * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。  
     * 针对所有的元素重复以上的步骤,除了最后一个。
     * 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 
     * @param arrys
     * @return
     */
    public Integer[] bubbleSortByAsc(Integer[] arrys){
        Integer[] clone = arrys.clone();
        for(int i=0;i<clone.length-1;i++){
            for(int j=0;j<clone.length-1-i;j++){
                if(clone[j]>clone[j+1]){
                    int temp=clone[j];
                    clone[j]=clone[j+1];
                    clone[j+1]=temp;
                }
            }
        }
        return clone;
    }

    /**
     * 冒泡降序
     * @param arrys
     * @return
     */
    public Integer[] bubbleSortByDesc(Integer[] arrys){
        Integer[] clone = arrys.clone();
        for(int i=0;i<clone.length-1;i++){
            for(int j=0;j<clone.length-1-i;j++){
                if(clone[j]>clone[j+1]){
                    int temp=clone[j];
                    clone[j]=clone[j+1];
                    clone[j+1]=temp;
                }
            }
        }
        return clone;
    }

2. 希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

====================================================
算法思想简单描述:

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。

下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。

希尔排序是不稳定的。

原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1]
对算法进行了少量修改,可以使得性能提升至O(n log2
n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据,所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i
+= step_size而不是i++)。

排序过程

图片 3

希尔排序图解.gif

最差时间复杂度 根据步长串行的不同而不同。O(nLog2 n)

最优时间复杂度 O(n)

平均时间复杂度 根据步长串行的不同而不同。

====================================================

实例2:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ShellSorter
{
    /// <summary>
    /// 希尔排序
    /// </summary>
    public class ShellSorter
{
        public void Sort(int[] list)
{
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3)
{
                for (int i = inc + 1; i <= list.Length; i += inc)
{
                    int t = list[i - 1];
                    int j = i;
                    while ((j > inc) && (list[j - inc - 1] > t))
{
                    list[j - 1] = list[j - inc - 1];
                    j -= inc;
}
                    list[j - 1] = t;
}
}
}
}
    class Program
{
        static void Main(string[] args)
{
            int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
            ShellSorter ii = new ShellSorter();
            ii.Sort(iArray);
            for (int m = 0; m <= iArray.Length - 1; m++)
                Console.WriteLine("{0}", iArray[m]);
            Console.ReadLine();   
}
}
}

2. 选择排序

思路分析:在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

function selectSort($arr) {
//双重循环完成,外层控制轮数,内层控制比较次数
$len=count($arr);
for($i=0; $i<$len-1; $i++) {
//先假设最小的值的位置
$p = $i;

for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是当前已知的最小值
if($arr[$p] > $arr[$j]) {
//比较,发现更小的,记录下最小值的位置;并且在下次比较时采用已知的最小值进行比较。
$p = $j;
}
}
//已经确定了当前的最小值的位置,保存到$p中。如果发现最小值的位置与当前假设的位置$i不同,则位置互换即可。
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//返回最终结果
return $arr;
}

交换排序—快速排序

描述:
选择一个基准元素,通常以第一个或最后一个,通过一趟排序,将待排序列分成两部分。一部分比基准元素小,另一部分比基准元素大或相等

    /**
     * 快速排序升序
     *
     * @param nums src
     * @return result
     */
    public Integer[] quickSortByAsc(Integer[] nums) {
        Integer[] clone = nums.clone();
        System.out.println("quick sort by Asc");
        quickSortByAsc(clone, 0, clone.length - 1);
        return clone;
    }

    public void quickSortByAsc(Integer[] nums, int low, int high) {
        if (low < high) {
            int middle = getMiddleAsc(nums, low, high);
            quickSortByAsc(nums, low, middle - 1);
            quickSortByAsc(nums, middle + 1, high);
        }
    }

    /**
     * 获取中轴位置(Asc升序)
     *
     * @param nums src
     * @param low  low
     * @param high high
     * @return position
     */
    private int getMiddleAsc(Integer[] nums, int low, int high) {
        int middleNum = nums[low];//取第一次传入的low位位中轴数
        while (low < high) {
            while (low < high && nums[high] >= middleNum) {//右边high游标不断前移,如果当前位置的数大于中轴上的数
                high--;
            }
            nums[low] = nums[high];//小的移到左边
            while (low < high && nums[low] <= middleNum) {//左边low游标不断后移,如果当前low位置的数小于中轴上的数
                low++;
            }
            nums[high] = nums[low];//大的移到右边
        }
        nums[low] = middleNum;//将中轴数放到正确的位置上
        return low;
    }

    /**
     * 快速排序降序
     *
     * @param nums src
     * @return result
     */
    public Integer[] quickSortByDesc(Integer[] nums) {
        Integer[] clone = nums.clone();
        System.out.println("quick sort by desc:");
        quickSortByDesc(clone, 0, clone.length - 1);
        return clone;
    }

    private void quickSortByDesc(Integer[] nums, int low, int high) {
        if (low < high) {
            int middle = getMiddleDesc(nums, low, high);
            quickSortByDesc(nums, low, middle - 1);//对中轴左边继续排序
            quickSortByDesc(nums, middle + 1, high);//对中轴右边继续排序
        }
    }

    /**
     * 获取中轴位置(Desc降序)
     *
     * @param nums src
     * @param low  low
     * @param high high
     * @return position
     */
    private int getMiddleDesc(Integer[] nums, int low, int high) {
        int middleNum = nums[low];//取第一次传入的low位位中轴数
        while (low < high) {
            while (low < high && nums[high] <= middleNum) {//右边high游标不断前移,如果当前位置的数小于中轴上的数
                high--;
            }
            nums[low] = nums[high];//大的数移到左边
            while (low < high && nums[low] >= middleNum) {//左边low游标不断后移,如果当前low位置的数大于中轴上的数
                low++;
            }
            nums[high] = nums[low];//小的数移到右边
        }
        nums[low] = middleNum;//将中轴数放到正确的位置上
        return low;

    }

3. 选择排序

====================================================
算法思想简单描述:

在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环
到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)–[n的平方]

选择排序(Selection sort)是一种简单直观的排序算法。

它的工作原理如下。

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,

然后,再从剩余未排序元素中继续寻找最小(大)元素,

然后放到已排序序列的末尾。

以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

实现过程

图片 4

选择排序图解.gif

最差时间复杂度 О(n)

最优时间复杂度 О(n)**

平均时间复杂度 О(n)

=====================================================

实例3:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace SelectionSorter
{
    public class SelectionSorter
{
        private int min;
        public void Sort(int[] list)
{
            //对数组list从第0个元素进行遍历
            for (int i = 0; i < list.Length - 1; ++i)
{
                //记录第i个小标
                min = i;
                //j=i+1;比较list[i]和list[i+1],如果list[i+1]<list[i],记录新的min=j;
                for (int j = i + 1; j < list.Length; ++j)
{
                    if (list[j] < list[min])
                min = j;
}
                //两个大小数交换
                int t = list [min];
                list[min] = list[i];
                list[i] = t;
}
}
}
    class Program
{
        static void Main(string[] args)
{
            int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
            SelectionSorter ii = new SelectionSorter();
                ii.Sort(iArray);
            for (int m = 0; m <= iArray.Length - 1; m++)
                Console.WriteLine("{0}", iArray[m]);
            Console.ReadLine();   
}
}
}

3.插入排序

思路分析:在要排序的一组数中,假设前面的数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

function insertSort($arr) {
$len=count($arr);
for($i=1, $i<$len; $i++) {
$tmp = $arr[$i];
//内层循环控制,比较并插入
for($j=$i-1;$j>=0;$j--) {
if($tmp < $arr[$j]) {
//发现插入的元素要小,交换位置,将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素,由于是已经排序好是数组,则前面的就不需要再次比较了。
break;
}
}
}
return $arr;
}

插入排序——直接插入排序

描述:
在排序的数组中,假设前面n-1(n>=2)个数已经排好顺序,现在将第n个数插入到前面的有序数组中,使得这n个数也是排好顺序。反复循环。直到排列完成。

    /**
     * 基本思想:每步将一个待排序的记录,按其顺序码大小插入到
     * 前面已经排序的字序列的合适位置(从后向前找到合适位置后),
     * 直到全部插入排序完为止。
     *
     * 从第一个元素开始,该元素可以认为已经被排序
     * 取出下一个元素,在已经排序的元素序列中从后向前扫描
     * 如果该元素(已排序)大于新元素,将该元素移到下一位置
     * 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     * @param nums
     */
    public Integer[] insertSortByAsc(Integer[] nums){
        System.out.println("insert sort by Asc:");
        Integer[] clone = nums.clone();
        for(int i=0;i<clone.length;i++){
            int temp=clone[i];//取出下个待插入排序的数
            int j=0;//插入的位置标记
            for(j=i;j>0&&temp<clone[j-1];j--){//满足待排序数小于前面的数条件,j--
                clone[j]=clone[j-1];//整体后移一位
            }
            clone[j]=temp;
        }
        return clone;
    }


    /**
     * 基本思想:每步将一个待排序的记录,按其顺序码大小插入到
     * 前面已经排序的字序列的合适位置(从后向前找到合适位置后),
     * 直到全部插入排序完为止。
     *
     * 从第一个元素开始,该元素可以认为已经被降序排序
     * 取出下一个元素,在已经排序的元素序列中从后向前扫描
     * 如果该元素(已排序)小于新元素,将该元素移到下一位置
     * 重复步骤3,直到找到已排序的元素大于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     * @param nums
     */
    public Integer[] insertSortByDesc(Integer[] nums){
        System.out.println("insert sort by Desc:");
        Integer[] clone = nums.clone();
        for(int i=0;i<clone.length;i++){
            int temp=clone[i];//取出下个待插入排序的数
            int j=0;//插入的位置标记
            for(j=i;j>0&&temp>clone[j-1];j--){//满足待排序数大于前面的数条件,j--
                clone[j]=clone[j-1];//整体后移一位
            }
            clone[j]=temp;
        }
        return clone;
    }

4. 冒泡排序

====================================================
算法思想简单描述:

依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数……直到比较最后两个数.第一趟结束,最小的

一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后……
由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.

冒泡排序(Bubble
Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。

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

冒泡排序对n个项目需要O(n^{2})的比较次数,且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的执行时间,但是两种法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要O(n^{2})次交换,而插入排序只要最多O(n)交换。

冒泡排序的实现(类似下面)通常会对已经排序好的数列拙劣地执行(O(n^{2})),而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时,使用一个旗标来表示有无需要交换的可能,也有可能把最好的复杂度降低到O(n)。在这个情况,在已经排序好的数列就无交换的需要。若在每次走访数列时,把走访顺序和比较大小反过来,也可以稍微地改进效率。有时候称为往返排序,因为算法会从数列的一端到另一端之间穿梭往返。

2.算法实现
1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

3.实现过程

图片 5

冒泡排序图解.gif

最差时间复杂度 O(n^2)

最优时间复杂度 O(n)

平均时间复杂度O(n^2)

====================================================

实例4:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Bubblesort
{
    /// <summary>
    /// 冒泡排序
    /// </summary>
    public class bubblesort
{
        public void BubbleSort(int[] R)
{
            int i, j, temp; //交换标志 
            bool exchange;
            for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序 
{
                exchange = false; //本趟排序开始前,交换标志应为假
                for (j = R.Length - 2; j >= i; j--)
{
                    if (R[j + 1] < R[j]) //交换条件
                   {
                       temp = R[j + 1];
                       R[j + 1] = R[j];
                       R[j] = temp;
                        exchange = true; //发生了交换,故将交换标志置为真 
}
}
                if (!exchange) //本趟排序未发生交换,提前终止算法 
{
                    break;
}
}
}
}
    class Program
{
        static void Main(string[] args)
{
            int[] iArray = new int[] { 1, 5, 3, 6, 10, 55 };
            bubblesort ii = new bubblesort();
             ii.BubbleSort(iArray);
            for (int m = 0; m <= iArray.Length - 1; m++)
                Console.WriteLine("{0}", iArray[m]);
            Console.ReadLine();   
}
}
}

4.快速排序

思路分析:选择一个基准元素,通常选择第一个元素或者最后一个元素。通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素。此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

function quickSort($arr) {
//先判断是否需要继续进行
$length = count($arr);
if($length <= 1) {
return $arr;
}
//选择第一个元素作为基准
$base_num = $arr[0];
//遍历除了标尺外的所有元素,按照大小关系放入两个数组内
//初始化两个数组
$left_array = array();  //小于基准的
$right_array = array();  //大于基准的
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//放入左边数组
$left_array[] = $arr[$i];
} else {
//放入右边
$right_array[] = $arr[$i];
}
}
//再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
//合并
return array_merge($left_array, array($base_num), $right_array);
}

插入排序——希尔排序

描述:将要排序的一组数按某个增量
d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差
d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到
1 时,进行直接插入排序后,排序完成。

    /**
     * 希尔排序升序
     * 基本思想:
     * 将数组拆分成d长度的小数组,最开始d长度为length/2
     * 对小数组插入排序
     * 再将d长度缩小为d/2
     * 重复操作,直到d=1
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] shellSortAsc(Integer[] nums) {
        System.out.println("shell sort by Asc:");
        Integer[] clone = nums.clone();
        for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次缩小二分之一
            for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d长度的段
                //对d长度的每组数进行插入排序,每组起始坐标为groupStarPosition
                for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
                    int temp = clone[j];
                    int k = 0;
                    for (k = j; k > groupStarPosition && temp < clone[k - 1]; k--) {
                        clone[k] = clone[k - 1];
                    }
                    clone[k] = temp;
                }
            }
        }
        return clone;
    }

    /**
     * 希尔排序升序
     * 基本思想:
     * 将数组拆分成d长度的小数组,最开始d长度为length/2
     * 对小数组插入排序
     * 再将d长度缩小为d/2
     * 重复操作,直到d=1
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] shellSortByDesc(Integer[] nums) {
        System.out.println("shell sort by Desc:");
        Integer[] clone = nums.clone();
        for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次缩小二分之一
            for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d长度的段
                //对d长度的每组数进行插入排序,每组起始坐标为groupStarPosition
                for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
                    int temp = clone[j];
                    int k = 0;
                    for (k = j; k > groupStarPosition && temp > clone[k - 1]; k--) {
                        clone[k] = clone[k - 1];
                    }
                    clone[k] = temp;
                }
            }
        }
        return clone;
    }

5. 快速排序

====================================================
算法思想简单描述:

快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序的基本概念是
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
下面通过一个例子来了解快速排序的具体含义: { 23, 45, 60, 10, 17,
101,12}
第一遍排序:

图片 6

快速排序图解.jpg

由此思想,我们可以实现快速排序的代码:

选择排序——直接选择排序

描述:排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

    /**
     * 选择排序(升序)
     * 每次选择一个最小值排在有序数组的后面一位上
     * 主要关心每次选择的最小值的位置与值,再将此位置与数值交换
     *
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] selectSortByAsc(Integer[] nums) {
        System.out.println("select sort by Asc:");
        Integer[] clone = nums.clone();
        int position = 0;//记录本次选择数的数组位置
        int value = 0;//记录本次选择的值
        for (int i = 0; i < clone.length; i++) {
            value = clone[i];//初始值为clone[i]
            for (int j = i; j < clone.length; j++) {
                //如果发现有值比当前选择的值小,position记录他在数组中的位置,更新value的值,进行下次比较
                if (clone[j] <= value) {
                    position = j;
                    value = clone[j];
                }
            }
            //将此次选择的最小值与clone[i]位置交换
            int temp = clone[i];
            clone[i] = value;
            clone[position] = temp;
        }
        return clone;
    }

    /**
     * 选择排序(降序)
     * 每次选择一个最大值排在有序数组的后面一位上
     * 主要关心每次选择的最大值的位置与值,再将此位置与起始选择位置交换
     *
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] selectSortByDesc(Integer[] nums) {
        System.out.println("select sort by Desc:");
        Integer[] clone = nums.clone();
        int position = 0;//记录本次选择数的数组位置
        int value = 0;//记录本次选择的值
        for (int i = 0; i < clone.length; i++) {
            value = clone[i];//初始值为clone[i]
            for (int j = i; j < clone.length; j++) {
                //如果发现有值比当前选择的值大,position记录他在数组中的位置,更新value的值,进行下次比较
                if (clone[j] >= value) {
                    position = j;
                    value = clone[j];
                }
            }
            //将此次选择的最小值与clone[i]位置交换
            int temp = clone[i];
            clone[i] = value;
            clone[position] = temp;
        }
        return clone;
    }

注意基准数据永远不变,永远是和基准数据进行比较,无论在什么位置,最后的目的就是把基准数据放在中间,小的放前面大的放后面。

实例5:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QuickSorter
{
    class Program
{
        static void Main(string[] args)
{
            int[] n = { 23, 45, 60, 10, 17, 101,12};
            QuickSort qs = new QuickSort();
            qs.QuickSortFunc(n, 0, n.Length - 1);
            for (int i = 0; i < n.Length; i++)
{
                Console.WriteLine(n[i]);
}
            Console.ReadLine(); 
}
}
    class QuickSort
{
        //方法一:
        private int Func(int[] n, int left, int right)
{
            int baseNum = n[left]; // 基准数据
            int i = left;
            int j = right;
            while (true)
{
                if (n[i] < baseNum && i < j)
{
                i++;
}
                else if (n[i] > baseNum && i < j)
{
                    int number = n[i];
                    n[i] = n[j];
                    n[j] = number;
                   j--;
}
                else if (n[j] < baseNum && i < j)
{
                    int number = n[i];
                   n[i] = n[j];
                   n[j] = number;
                   i++;
}
                else if (n[j] > baseNum && i < j)
{
                   j--;
}
                else if (i == j)
{
                   n[i] = baseNum;
                    break;
}
}
            return i;
}
        public void QuickSortFunc(int[] n, int left, int right)
{
            //左下标一定小于右下标,否则就超越了
            if (left < right)
{
                //对数组进行分割,取出下次分割的基准标号 
                int i = Func(n, left, right);
                //对“基准标号“左侧的一组数值进行递归的切割,以至于将这些数值完整的排序
QuickSortFunc(n, left, i - 1);
                //对“基准标号“右侧的一组数值进行递归的切割,以至于将这些数值完整的排序
QuickSortFunc(n, i + 1, right);
}
}
        //end 方法一
        //方法二:其实我们还可以取中间的数作为基准,具体示例如下:
        private void Sort(int[] numbers, int left, int right)
{
            //左边索引小于右边,则还未排序完成   
            if (left < right)
{
                //取中间的元素作为比较基准,小于他的往左边移,大于他的往右边移   
                int middle = numbers[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true)
{
                    while (numbers[++i] < middle && i < right) ;
                    while (numbers[--j] > middle && j > 0) ;
                    if (i >= j)
                        break;
                   Swap(numbers, i, j);
}
                   Sort(numbers, left, i - 1);
                   Sort(numbers, j + 1, right);
                for (int k = 0; k < numbers.Length; k++)
{
                    Console.WriteLine(numbers[k]);
}
                Console.ReadLine();
}
}
        private void Swap(int[] numbers, int i, int j)
{
            int number = numbers[i];
                   numbers[i] = numbers[j];
                   numbers[j] = number;
}
        //end 方法二
}
}

选择排序——堆排序(待续)

归并排序

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    /**
     * 归并排序升序
     *
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] mergeSortAsc(Integer[] nums) {
        System.out.println("merge sort By Asc:");
        Integer[] clone = nums.clone();
        mergeSortAsc(clone, 0, clone.length - 1);
        return clone;
    }

    /**
     * low 到high 元素归并
     *
     * @param nums src numbers
     * @param low  归并元素起始位置
     * @param high 归并元素结束位置
     */
    public void mergeSortAsc(Integer[] nums, int low, int high) {

        if (low < high) {
            int middle = (low + high) / 2;
            mergeSortAsc(nums, low, middle);//对左边归并排序
            mergeSortAsc(nums, middle + 1, high);//对右边归并排序
            mergeAsc(nums, low, middle, high);//归并
        }
    }

    /**
     * 归并操作,将有序的两边的子序列合并成整体有序的数
     *
     * @param nums   待排序数组
     * @param low    待排的开始位置
     * @param middle 待排中间位置
     * @param high   待排结束位置
     */
    public void mergeAsc(Integer[] nums, int low, int middle, int high) {
        //辅助数组,用于存储新排序好的数组
        Integer[] temp = new Integer[high - low + 1];
        //左指针
        int left = low;
        //右指针
        int right = middle + 1;
        //辅助数组的标记
        int k = 0;
        // 把较小的数先移到新数组中
        while (left <= middle && right <= high) {
            if (nums[left] < nums[right]) {
                temp[k] = nums[left];
                left++;
                k++;
            } else {
                temp[k] = nums[right];
                right++;
                k++;
            }
        }

        // 把左边剩余的数移入数组
        while (left <= middle) {
            temp[k++] = nums[left++];
        }

        // 把右边剩余的数移入数组
        while (right <= high) {
            temp[k++] = nums[right++];
        }

        // 把新数组中的数覆盖回到nums数组
        for (int i = 0; i < temp.length; i++) {
            nums[low + i] = temp[i];
        }

    }

    /**
     * 归并排序(降序)
     *
     * @param nums src numbers
     * @return result numbers
     */
    public Integer[] mergeSortDesc(Integer[] nums) {
        System.out.println("merge sort by Desc:");
        Integer[] clone = nums.clone();
        mergeSortDesc(clone, 0, clone.length - 1);
        return clone;
    }

    /**
     * low 到high 元素desc归并
     *
     * @param nums src numbers
     * @param low  归并元素起始位置
     * @param high 归并元素结束位置
     */
    public void mergeSortDesc(Integer[] nums, int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2;
            mergeSortDesc(nums, low, middle);
            mergeSortDesc(nums, middle + 1, high);
            mergeDesc(nums, low, middle, high);
        }
    }

    /**
     * 归并操作,将有序的两边的子序列合并成整体有序的数
     *
     * @param nums   待排序数组
     * @param low    待排的开始位置
     * @param middle 待排中间位置
     * @param high   待排结束位置
     */
    public void mergeDesc(Integer[] nums, int low, int middle, int high) {
        //辅助数组,用于存储新排序好的数组
        Integer[] temp = new Integer[high - low + 1];
        //左指针
        int left = low;
        //右指针
        int right = middle + 1;
        //辅助数组的标记
        int k = 0;
        // 把较大的数先移到新数组中
        while (left <= middle && right <= high) {
            if (nums[left] > nums[right]) {
                temp[k] = nums[left];
                left++;
                k++;
            } else {
                temp[k] = nums[right];
                right++;
                k++;
            }
        }

        // 把左边剩余的数移入数组
        while (left <= middle) {
            temp[k++] = nums[left++];
        }

        // 把右边剩余的数移入数组
        while (right <= high) {
            temp[k++] = nums[right++];
        }

        // 把新数组中的数覆盖回到nums数组
        for (int i = 0; i < temp.length; i++) {
            nums[low + i] = temp[i];
        }

    }

分配排序(待续)

发表评论

电子邮件地址不会被公开。 必填项已用*标注