选择排序 订阅
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 [1] 展开全文
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 [1]
信息
应用领域
计算机,数学 [1]
外文名
Selection Sort [1]
最好复杂度
O(n^2) [1]
方    法
通过比较 [1]
中文名
选择排序 [1]
最差复杂度
O(n^2) [1]
性    质
不稳定的排序方法 [1]
选择排序选择排序思路
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 [1]  [2] 
收起全文
精华内容
下载资源
问答
  • 选择排序

    万次阅读 多人点赞 2012-08-28 11:18:16
    今天将会写完选择排序 和 插入排序,本文主在选择排序。 一. 算法描述 选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数

        昨日写完冒泡排序,和大多数人的感觉一样,太简单,丝毫没有挑战性。但楼主是一个追求踏实平稳的人,希望地基牢固,也为方便后面学习和研究更加高深的算法。但在研究效率上还有待提高,楼主一定好好努力。今天将会写完选择排序 和 插入排序,本文主在选择排序。

    一. 算法描述

        选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成。

    以下面5个无序的数据为例:

    56 12 80 91 20(文中仅细化了第一趟的选择过程)

    第1趟:12 56 80 91 20

     

    第2趟:12 20 80 91 56

    第3趟:12 20 56 91 80

    第4趟:12 20 56 80 91

    二. 算法分析

    平均时间复杂度:O(n2)

    空间复杂度:O(1)  (用于交换和记录索引)

    稳定性:不稳定 (比如序列【5, 5, 3】第一趟就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)

    三. 算法实现

     

    //交换data1和data2所指向的整形
    void DataSwap(int* data1, int* data2)
    {
    	int temp = *data1;
    	*data1 = *data2;
    	*data2 = temp;
    }
    
    /********************************************************
    *函数名称:SelectionSort
    *参数说明:pDataArray 无序数组;
    *		   iDataNum为无序数据个数
    *说明:    选择排序
    *********************************************************/
    void SelectionSort(int* pDataArray, int iDataNum)
    {
    	for (int i = 0; i < iDataNum - 1; i++)    //从第一个位置开始
    	{
    		int index = i;
    		for (int j = i + 1; j < iDataNum; j++)    //寻找最小的数据索引 
    			if (pDataArray[j] < pDataArray[index])
    				index = j;
    
    		if (index != i)    //如果最小数位置变化则交换
    			DataSwap(&pDataArray[index], &pDataArray[i]);
    	}
    }

     

    最后是个人微信公众号,文章CSDN和微信公众号都会发,欢迎一起讨论。
    在这里插入图片描述

     

     

     

     

    展开全文
  • 算法 - 选择排序(C#)

    万次阅读 多人点赞 2019-02-01 15:05:30
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 每一趟从待排序的数据元素中选出最小... * 选择排序是不稳定的排序算法。 */ namespace SelectionSort { ...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
     * 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完为止。
     * 选择排序是不稳定的排序算法。
     */
    
    namespace SelectionSort
    {
        using System;
    
        /// <summary>
        /// The program.
        /// </summary>
        public static class Program
        {
            /// <summary>
            /// The main.
            /// </summary>
            public static void Main()
            {
                int[] a = {1, 6, 4, 2, 8, 7, 9, 3, 10, 5};
    
                Console.WriteLine("Before Selection Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
    
                Console.WriteLine("\r\n\r\nIn Selection Sort:");
                SelectionSort(a);
    
                Console.WriteLine("\r\nAfter Selection Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
            }
    
            /// <summary>
            /// The selection sort.
            /// </summary>
            /// <param name="a">
            /// The a.
            /// </param>
            private static void SelectionSort(int[] a)
            {
                for (int i = 0; i < a.Length - 1; i++)
                {
                    // 存储最小元素的index。
                    int min = i;
    
                    // 寻找最小元素的index。
                    for (int j = i + 1; j < a.Length; j++)
                    {
                        if (a[j] < a[min])
                        {
                            min = j;
                        }
                    }
    
                    int tmp = a[min];
                    a[min] = a[i];
                    a[i] = tmp;
    
                    // 打印数组。
                    foreach (int k in a)
                    {
                        Console.Write(k + " ");
                    }
    
                    Console.WriteLine(string.Empty);
                }
            }
        }
    }
    
    // Output:
    /*
    Before Selection Sort:
    1 6 4 2 8 7 9 3 10 5
    
    In Selection Sort:
    1 6 4 2 8 7 9 3 10 5
    1 2 4 6 8 7 9 3 10 5
    1 2 3 6 8 7 9 4 10 5
    1 2 3 4 8 7 9 6 10 5
    1 2 3 4 5 7 9 6 10 8
    1 2 3 4 5 6 9 7 10 8
    1 2 3 4 5 6 7 9 10 8
    1 2 3 4 5 6 7 8 10 9
    1 2 3 4 5 6 7 8 9 10
    
    After Selection Sort:
    1 2 3 4 5 6 7 8 9 10
    */

     

    展开全文
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...


    1. 插入排序

    步骤:

    1.从第一个元素开始,该元素可以认为已经被排序
    2.取下一个元素tem,从已排序的元素序列从后往前扫描
    3.如果该元素大于tem,则将该元素移到下一位
    4.重复步骤3,直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
    6.重复步骤2~5

    动图演示如下:在这里插入图片描述
    思路:
      在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
      但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码如下:

    void InsertSort(int* arr, int n)
    {
    	for (int i = 0; i < n - 1; ++i)
    	{
    		//记录有序序列最后一个元素的下标
    		int end = i;
    		//待插入的元素
    		int tem = arr[end + 1];
    		//单趟排
    		while (end >= 0)
    		{
    			//比插入的数大就向后移
    			if (tem < arr[end])
    			{
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			//比插入的数小,跳出循环
    			else
    			{
    				break;
    			}
    		}
    		//tem放到比插入的数小的数的后面
    		arr[end  + 1] = tem;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
    	}
    }
    

    时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
          最好情况下为O(N),此时待排序列为升序,或者说接近升序。
    空间复杂度:O(1)

    2.希尔排序

    步骤:
    1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
    2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。
    动图如下:
    在这里插入图片描述
    思路:
    希尔排序,先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序,此时插入排序的时间复杂度为O(N),

    代码如下:

    //希尔排序
    void ShellSort(int* arr, int n)
    {
    	int gap = n;
    	while (gap>1)
    	{
    		//每次对gap折半操作
    		gap = gap / 2;
    		//单趟排序
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			int tem = arr[end + gap];
    			while (end >= 0)
    			{
    				if (tem < arr[end])
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tem;
    		}
    	}
    }
    

    时间复杂度平均:O(N^1.3)
    空间复杂度:O(1)

    3.选择排序

    思路:
    每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
    实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    动图如下:
    在这里插入图片描述
    代码如下:

    //选择排序
    void swap(int* a, int* b)
    {
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }
    void SelectSort(int* arr, int n)
    {
    	//保存参与单趟排序的第一个数和最后一个数的下标
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
    		//保存最大值的下标
    		int maxi = begin;
    		//保存最小值的下标
    		int mini = begin;
    		//找出最大值和最小值的下标
    		for (int i = begin; i <= end; ++i)
    		{
    			if (arr[i] < arr[mini])
    			{
    				mini = i;
    			}
    			if (arr[i] > arr[maxi])
    			{
    				maxi = i;
    			}
    		}
    		//最小值放在序列开头
    		swap(&arr[mini], &arr[begin]);
    		//防止最大的数在begin位置被换走
    		if (begin == maxi)
    		{
    			maxi = mini;
    		}
    		//最大值放在序列结尾
    		swap(&arr[maxi], &arr[end]);
    		++begin;
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N^2)
    空间复杂度:O(1)

    4.冒泡排序

    思路:
    左边大于右边交换一趟排下来最大的在右边

    动图如下:
    在这里插入图片描述
    代码如下:

    //冒泡排序
    void BubbleSort(int* arr, int n)
    {
    	int end = n;
    	while (end)
    	{
    		int flag = 0;
    		for (int i = 1; i < end; ++i)
    		{
    			if (arr[i - 1] > arr[i])
    			{
    				int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N)
    空间复杂度:O(1)

    5.堆排序

    堆排可看之间这篇博文----->[堆排]

    6.快速排序

    5.1 hoare版本(左右指针法)

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
    3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
    4.此时key的左边都是小于key的数,key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int* arr, int begin, int end)
    {
    	//只有一个数或区间不存在
    	if (begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	//选左边为key
    	int keyi = begin;
    	while (begin < end)
    	{
    		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    		while (arr[end] >= arr[keyi] && begin < end)
    		{
    			--end;
    		}
    		//左边选大
    		while (arr[begin] <= arr[keyi] && begin < end)
    		{
    			++begin;
    		}
    		//小的换到右边,大的换到左边
    		swap(&arr[begin], &arr[end]);
    	}
    	swap(&arr[keyi], &arr[end]);
    	keyi = end;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort(arr, left, keyi - 1);
    	QuickSort(arr,keyi + 1,right);
    }
    

    时间复杂度:
    在这里插入图片描述
    快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:在这里插入图片描述

    5.2 挖坑法

    5.2.1 递归

    思路:
    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
    2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序法  挖坑法
    void QuickSort1(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int left = begin,right = end;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		//找小
    		while (arr[end] >= key && begin < end)
    		{
    			--end;
    		}
    		//小的放到左边的坑里
    		arr[begin] = arr[end];
    		//找大
    		while (arr[begin] <= key && begin < end)
    		{
    			++begin;
    		}
    		//大的放到右边的坑里
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int keyi = begin;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort1(arr, left, keyi - 1);
    	QuickSort1(arr, keyi + 1, right);
    }
    

    5.2.2 非递归

    //单趟排
    int PartSort(int* arr, int begin, int end)
    {
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (key <= arr[end] && begin < end)
    		{
    			--end;
    		}
    		arr[begin] = arr[end];
    		while (key >= arr[begin] && begin < end)
    		{
    			++begin;
    		}
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int meeti = begin;
    	return meeti;
    }
    
    void QuickSortNoR(int* arr, int begin, int end)
    {
    	stack<int> st;
    	//先入右边
    	st.push(end);
    	//再入左边
    	st.push(begin);
    	while (!st.empty())
    	{
    		//左区间
    		int left = st.top();
    		st.pop();
    		//右区间
    		int right = st.top();
    		st.pop();
    		//中间数
    		int mid = PartSort(arr, left, right);
    		//当左区间>=mid-1则证明左区间已经排好序了
    		if (left < mid - 1)
    		{
    			st.push(mid - 1);
    			st.push(left);
    		}
    		//当mid+1>=右区间则证明右区间已经排好序
    		if (right > mid + 1)
    		{
    			st.push(right);
    			st.push(mid + 1);
    		}
    	}
    }
    

    5.3 前后指针法

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、起始时,prev指针指向序列开头,cur指针指向prev+1。
    3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作

    //快速排序法  前后指针版本
    void QuickSort2(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int cur = begin, prev = begin - 1;
    	int keyi = end;
    	while (cur != keyi)
    	{
    		if (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			swap(&arr[cur], &arr[prev]);
    		}
    		++cur;
    	}
    	swap(&arr[++prev],&arr[keyi]);
    	keyi = prev;
    	//[begin,keyi -1]keyi[keyi+1,end]
    	QuickSort2(arr, begin, keyi - 1);
    	QuickSort2(arr, keyi + 1, end);
    
    }
    
    展开全文
  • 冒泡排序、选择排序、插入排序、快速排序、希尔排序

    一、冒泡排序

    1.1 冒泡排序基础【必会知识】

      冒泡排序是比较基础的排序算法之一,其思想是相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。整个过程如同气泡冒起,因此被称作冒泡排序。
      冒泡排序的步骤是比较固定的:

    1>比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2>每趟从第一对相邻元素开始,对每一对相邻元素作同样的工作,直到最后一对。
    3>针对所有的元素重复以上的步骤,除了已排序过的元素(每趟排序后的最后一个元素),直到没有任何一对数字需要比较。

      此处引用网上一张比较经典的gif来展示冒泡排序的整个过程:

      冒泡排序的常规实现代码如下:

    	public static void bubbleSort(int[] arr) {
    		/*判断数组为空或为一个元素的情况,即边界检查*/
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		
    		/*规定每次两两比较的末尾元素的位置,最多为数组的最后一个位置*/
    		for (int end = arr.length - 1; end > 0; end--) {
    			/*从第一个元素开始,两两进行比较,如果前面的元素大于后面的
    			  元素,就交换,最终的结果就是最大的数在最后面
    			*/
    			for (int i = 0; i < end; i++) {
    				if (arr[i] > arr[i + 1]) {
    					swap(arr, i, i + 1);
    				}
    			}
    		}
    	}
    
    	public static void swap(int[] arr, int i, int j) {
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}
    

    1.2 冒泡排序优化

      上个章节介绍了冒泡排序的常规实现,但是这种最简单的排序是存在着不必要的比较动作的。稍微修改上述代码,就可以查看每次比较后的结果:

            int[ ] array=new int[ ]{5,2,3,9,4};
            /*外循环为排序趟数,array.length个数进行array.length-1趟 */
            for(int i=0;i<array.length-1;i++){
            	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
                for(int j=0;j<array.length-1-i;j++){
                	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                    if(array[j]>array[j+1]){
                        int temp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=temp;
                    }
                    /*查看每趟比较后的数组元素*/
                    System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                    for(int k=0;k<array.length;k++){
                        System.out.print(array[k]+" ");
                    }
                    System.out.println();
                }
            }
    

      该代码的输出结果为:

    第 1 趟,第 1 次比较后的结果:
    2 5 3 9 4
    第 1 趟,第 2 次比较后的结果:
    2 3 5 9 4
    第 1 趟,第 3 次比较后的结果:
    2 3 5 9 4
    第 1 趟,第 4 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 1 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 2 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 3 次比较后的结果:
    2 3 4 5 9
    第 3 趟,第 1 次比较后的结果:
    2 3 4 5 9
    第 3 趟,第 2 次比较后的结果:
    2 3 4 5 9
    第 4 趟,第 1 次比较后的结果:
    2 3 4 5 9

      从上面的测试结果可以看出,从第2趟第3次比较后,数组元素已经处于有序状态,此后所有的比较都不必进行。

    1.2.1 外循环优化

      第一种优化就基于上面的测试结果来进行,如果某次比较过程中,发现没有任何元素移动,则不再进行接下来的比较。具体的做法是在每趟比较时,引入一个boolean型变量isSwap,来判断下次比较还有没有必要进行。示例代码如下:

            int[ ] array=new int[ ]{5,2,3,9,4};
            /*外循环为排序趟数,array.length个数进行array.length-1趟 */
            for(int i=0;i<array.length-1;i++){
            	boolean isSwap=false;
            	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
                for(int j=0;j<array.length-1-i;j++){
                	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                    if(array[j]>array[j+1]){
                        int temp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=temp;
                        isSwap=true;
                    }
                    /*查看每趟比较后的数组元素*/
                    System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                    for(int k=0;k<array.length;k++){
                        System.out.print(array[k]+" ");
                    }
                    System.out.println();
                }
                /*如果没有交换过元素,则已经有序,不再进行接下来的比较*/
                if(!isSwap){
                	break;
                }
            }
    

      测试结果如下:

    第 1 趟,第 1 次比较后的结果:
    2 5 3 9 4
    第 1 趟,第 2 次比较后的结果:
    2 3 5 9 4
    第 1 趟,第 3 次比较后的结果:
    2 3 5 9 4
    第 1 趟,第 4 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 1 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 2 次比较后的结果:
    2 3 5 4 9
    第 2 趟,第 3 次比较后的结果:
    2 3 4 5 9
    第 3 趟,第 1 次比较后的结果:
    2 3 4 5 9
    第 3 趟,第 2 次比较后的结果:
    2 3 4 5 9

      从上面的测试结果可以看出,已经对排序过程进行了优化,因为没有进行第4趟比较。也许有人会有疑问“第2趟比较结束后,数组已经有序了,为什么还要进行第3次比较”?之所以对此有疑问,可能是没太清楚isSwap变量的作用,该变量的作用是“假如本趟比较过程中没有交换发生,则不必进行下一趟比较”,在第2趟比较过程中,发生了交换动作,所以第3趟比较仍会进行。

    1.2.2 内循环优化

      第一种优化方式比较容易理解,但同时也存在着缺点:某趟比较只要开始,哪怕数组元素已经有序,也要把该趟的所有次比较完。也就是说,第一种优化方式,只能在“趟”的级别上优化。
      第二种优化方式,也就是要实现在“次”的级别进行优化,其思路是“记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可”。示例代码为:

            int[ ] array = new int[ ]{5,2,3,7,9};
            int position = array.length - 1;
            /*外循环为排序趟数,array.length个数进行array.length-1趟 */
            for(int i = 0;i<array.length-1;i++){
            	boolean isSwap = false;
            	/*用来记录最后一次交换的位置*/
            	int newPosition = 0;
            	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
                for(int j = 0;j<position;j++){
                	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                    if(array[j]>array[j+1]){
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                        isSwap = true;
                        /*记录最后一次交换的位置*/
                        newPosition = j;
                    }
                    /*查看每趟比较后的数组元素*/
                    System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
                    for(int k = 0;k<array.length;k++){
                        System.out.print(array[k]+" ");
                    }
                    System.out.println();
                }
                /*如果没有交换过元素,则已经有序,不再进行接下来的比较*/
                if(!isSwap){
                	break;
                }
                /*下趟比较所需要比较到的位置*/
                position = newPosition;
            }
    

      测试结果如下:

    第 1 趟,第 1 次比较后的结果:
    2 5 3 7 9
    第 1 趟,第 2 次比较后的结果:
    2 3 5 7 9
    第 1 趟,第 3 次比较后的结果:
    2 3 5 7 9
    第 1 趟,第 4 次比较后的结果:
    2 3 5 7 9
    第 2 趟,第 1 次比较后的结果:
    2 3 5 7 9

      从上面的测试结果可以看出,在第2趟进行了1次比较后,数组元素已经处于有序状态,此时便不再进行接下来的比较。

    1.2.3 双向遍历

      上面的两种优化都是单向遍历比较的,然而在很多时候,遍历的过程可以从两端进行,从而提升效率。因此在冒泡排序中,其实也可以进行双向循环,正向循环把最大元素移动到数组末尾,逆向循环把最小元素移动到数组首部。该种排序方式也叫双向冒泡排序,也叫鸡尾酒排序。
      关于此种排序优化,示例代码如下:

    	static void bubbleSort(int[] array) {
            int arrayLength = array.length;
            
            int preIndex = 0;
            int backIndex = arrayLength - 1;
            while(preIndex < backIndex) {
                preSort(array, arrayLength, preIndex);
                preIndex++;
                
                if (preIndex >= backIndex) {
                    break;
                }
                
                backSort(array, backIndex);
                backIndex--;
            }
        }
        
        // 从前向后排序
    	static void preSort(int[] array, int length, int preIndex) {
            for (int i = preIndex + 1; i < length; i++) {
                if (array[preIndex] > array[i]) {
                    swap(array, preIndex, i);
                }
            }
        }
        
        // 从后向前排序
    	static void backSort(int[] array, int backIndex) {
            for (int i = backIndex - 1; i >= 0; i--) {
                if (array[i] > array[backIndex]) {
                    swap(array, i, backIndex);
                }
            }
        }
    	
    	static void swap (int[] arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    

    1.3 冒泡排序的稳定性、复杂度和适用场景

    1.3.1 稳定性

      在冒泡排序中,遇到相等的值,是不进行交换的,只有遇到不相等的值才进行交换,所以是稳定的排序方式。

    1.3.2 时间复杂度

      如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序),一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:
            
      冒泡排序最好的时间复杂度为O(n)。

      如果待排序序列是反序(如我们希望的结果是升序,待排序序列是降序)的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
            在这里插入图片描述
      冒泡排序的最坏时间复杂度为O(n2)。
      综上,因此冒泡排序总的平均时间复杂度为O(n2)。

    1.3.3 适用场景

      冒泡排序适用于数据量很小的排序场景,因为冒泡的实现方式较为简单。

    二、选择排序

    2.1 选择排序基础【必会知识】

      选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置知道未排序元素个数为0。
      选择排序的步骤:

    1>首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
    2>再从剩余未排序元素中继续寻找最小(大)元素,然后放到未排序序列的起始位置。
    3>重复第二步,直到所有元素均排序完毕。

      此处引用网上一张比较经典的gif来展示选择排序的整个过程:

      用代码来实现上述过程,示例如下:

    	public static void selectionSort(int[] arr) {
    		/*判断数组为空或为一个元素的情况,即边界检查*/
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    
    		/*每次要进行比较的两个数,的前面那个数的下标*/
    		for (int i = 0; i < arr.length - 1; i++) { 
    			//min变量保存该趟比较过程中,最小元素所对应的索引,
    			//先假设前面的元素为最小元素
    			int minIndex = i;
    			/*每趟比较,将前面的元素与其后的元素逐个比较*/
    			for (int j = i + 1; j < arr.length; j++) {
    				//如果后面的元素小,将后面元素的索引极为最小值的索引
    				if(arr[j] < arr[minIndex]) {
    					minIndex = j;
    				}
    			}
    			//然后交换此次查找到的最小值和原始的最小值
    			swap(arr, i, minIndex);
    		}
    	}
    
    	public static void swap(int[] arr, int i, int j) {
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}
    

    2.2 选择排序优化

    2.2.1 选择排序优化图示

      选择排序的优化思路一般是在一趟遍历中,同时找出最大值与最小值,放到数组两端,这样就能将遍历的趟数减少一半。第一次选择最大值与最小值,过程如下:
          

    2.2.2 选择排序优化实现

      示例代码如下:

            /*初始化左端、右端元素索引*/
    	    int left = 0;
    	    int right = len - 1;
    	    while (left < right){
    	    	/*初始化最小值、最大值元素的索引*/
    	        int min = left;
    	        int max = right;
    	        for (int i = left; i <= right; i++){
    	        	/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
    	            if (arr[i] < arr[min])
    	                min = i;
    	            if (arr[i] > arr[max])
    	                max = i;
    	        }
    	        /*最大值放在最右端*/
    	        int temp = arr[max];
    	        arr[max] = arr[right];
    	        arr[right] = temp;
    	        /*此处是先排最大值的位置,所以得考虑最小值(arr[min])在最大位置(right)的情况*/
    	        if (min == right)
    	            min = max;
    	        /*最小值放在最左端*/
    	        temp = arr[min];
    	        arr[min] = arr[left];
    	        arr[left] = temp;
    	        /*每趟遍历,元素总个数减少2,左右端各减少1,left和right索引分别向内移动1*/
    	        left++;
    	        right--;
    	    }
    

    2.3 选择排序的稳定性、复杂度及适用场景

    2.3.1 稳定性

      在选择排序中,每趟都会选出最大元素与最小元素,然后与两端元素交换,此时,待排序序列中如果存在与原来两端元素相等的元素,稳定性就可能被破坏。如[5,3,5,2,9],在array[0]与array[3]元素交换时,序列的稳定性就被破坏了,所以选择排序是一种不稳定的排序算法。

    2.3.2 时间复杂度

      选择排序的时间复杂度为O(n2)。

    2.3.3 适用场景

      待排序序列中,元素个数较少时。

    三、插入排序

    3.1 插入排序基础【必会知识】

      插入排序也是一种常见的排序算法,插入排序的思想是:将初始数据分为有序部分和无序部分,每一步将一个无序部分的数据插入到前面已经排好序的有序部分中,直到插完所有元素为止。
      插入排序的步骤如下:每次从无序部分中取出一个元素,与有序部分中的元素从后向前依次进行比较,并找到合适的位置,将该元素插到有序组当中。

      假如有[5,2,3,9,4,7]六个元素,下面就以排序过程中的一个步骤(此时有序部分为[2,3,5,9],无序部分为[4,7],接下来要把无序部分的“4”元素插入到有序部分),来展示一下插入排序的运行过程。

    1. 首先,原始的数组元素是这样的。
            
        其中,浅绿色代表有序部分,黄色代表无序部分。
    2. 在无序部分中挑出要插入到有序部分中的元素。
            
    3. 将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 9,所以9向后移,4向前移。
            
    4. 继续将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 5,所以5向后移,4继续向前移。
            
    5. 继续将4与3比较。由于4 > 3,所以不再向前比较,插入到当前位置。
            
    6. 此时有序部分,由[2,3,5,9]变成[2,3,4,5,9]。
            

      将上述过程用代码实现,示例如下:

    	public static void insertionSort(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		
    		//每次将从0-i位置的元素进行排序
    		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
    			//int j = i - 1; j >= 0表示左边位置的边界条件
    			//arr[j] > arr[j + 1]表示最右边的数与相邻数的比较
    			//j--表示将这个过程向左推进
    			//swap(arr, j, j + 1)表示进行两个相邻数比较时,左边的数大于右边数时,才交换否则不交换
    			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
    				swap(arr, j, j + 1);
    			}
    		}
    	}
    
    	public static void swap(int[] arr, int i, int j) {
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}
    

    3.2 插入排序优化

      插入排序的优化方式一般有两种:折半插入排序和2-路插入排序。

    3.2.1 折半插入排序

      该类优化有二分的思想,是在将待排序的元素与有序部分的元素比较时,不再挨个比较,而是用二分折中的方式进行比较,加快比较效率。示例代码如下:

    	    int j,low,mid,high,temp;
    	    for(int i = 1;i<n;i++){
    	        low = 0;
    	        high = i-1;
    	        temp = arr[i];
    	        /*找到合适的插入位置high+1,如果中间位置元素
    	         *比要插入元素大,则查找区域向低半区移动,否
    	         *则向高半区移动
    	         */
    	        while(low <= high){
    	            mid = (low+high)/2;
    	            if(arr[mid]>temp){
    	                high = mid-1;
    	            }else{
    	                low = mid+1;
    	            }
    	        }
    	        /*high+1后的元素后移*/
    	        for(j = i-1;j >= high+1;j--)    
    	        {
    	            arr[j+1] = arr[j];
    	        }
    	        /*将元素插入到指定位置*/
    	        arr[j+1] = temp;    
    	    }
    

    3.2.2 2-路插入排序

      该中方式是在折半插入排序的基础上再进行改进的算法,其目的是减少排序过程中移动记录的次数,付出的代价是n个记录的辅助空间。
      假设原数组为 arr,另设一个相同类型的数组 tempArr,先将 arr[0] 赋值给 tempArr[0],并将tempArr[0] 看成是在有序序列中处于中间位置的元素,然后从 arr[1] 起一次插入到 tempArr[1] 之前或之后的有序序列中。
      先将待插元素和tempArr[0] 做比较,若小于tempArr[0],则插入tempArr[0] 之前的有序部分;反之,将其插入tempArr[0] 之后的有序部分中。在实现算法时,可将tempArr看成一个循环数组,并设 first 和last分别指向排序过程中得到的有序序列中的第一个元素和最后一个元素在tempArr中的位置。示例代码如下:

            int j, first, last, mid;
            /*临时数组*/
            int[ ] tempArr =new int[len];        
            tempArr[0] = arr[0];
            /*first和last分别指临时数组tempArr中排好序的元素的第一个和最后一个位置*/
            first = last = 0;       
    
            for(int i = 1; i<len; i++){
            	/*j 是调整系数*/
                if(first > last){
                    j = len;        
                }else{
                    j = 0;
                }
                /*tempArr中间元素的位置*/
                mid = ((first+last+j)/2)%len; 
                /*arr[i]应该插入在tempArr的前半部分*/
                if(arr[i] < tempArr[mid]){      
                	/*j指向tempArr数组中的第一个元素*/
                    j = first;    
                    /*first 前移,取余是为了实现循环数组效果*/
                    first = (first-1+len)%len;  
                    /*待插元素大于 j 所指元素*/
                    while(arr[i] > tempArr[j]){    
                    	/*j 所指元素前移,取余是为了实现循环数组效果*/
                    	tempArr[(j-1+len)%len] = tempArr[j];  
                    	/*j 指向下一个元素*/
                        j = j+1;               
                    }
                    /*移动结束,待插元素插在tempArr[j]前*/
                    tempArr[(j-1+len)%len] = arr[i];    
                /*arr[i]应该插入在tempArr的后半部分*/
                }else{   
                	/*j指向tempArr数组中的最后一个元素*/
                    j = last;    
                    /*last后移, 指向插入后的最后一个元素*/
                    last++;            
                    /*待插元素小于 j 所指元素*/
                    while(arr[i] < tempArr[j]){  
                    	/*j 所指元素后移*/
                    	tempArr[(j+1)%len] = tempArr[j]; 
                    	/*j 指向上一个元素*/
                        j = (j-1+len)%len;         
                    }
                    /*移动结束,待插元素插在tempArr[j]后*/
                    tempArr[(j+1)%len] = arr[i]; 
                }
            }
            
            /*把在tempArr中排好序的元素依次赋给arr*/
            for(int i = 0; i < len; i++){                    
            	arr[i] = tempArr[(first+i)%len];
            }
    

    3.3 插入排序的稳定性、复杂度和适用场景

    3.3.1 稳定性

      在使用插入排序时,元素从无序部分移动到有序部分时,必须是不相等(大于或小于)时才会移动,相等时不处理,所以直接插入排序是稳定的。

    3.3.2 时间复杂度

      在插入排序中,当待排序序列是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n- 1次,时间复杂度为O(n)。
      最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(n2)。
      平均来说,array[1…j-1]中的一半元素小于array[j],一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样,是O(n2)。

    3.3.3 适用场景

      待排序序列的元素个数不多(<=50),且元素基本有序。

    四、快速排序

    4.1 快速排序基础【必会知识】

      快速排序也是一种较为基础的排序算法,其效率比冒泡排序算法有大幅提升。因为使用冒泡排序时,一趟只能选出一个最值,有n个元素最多就要执行n - 1趟比较。而使用快速排序时,一次可以将所有元素按大小分成两堆,也就是平均情况下需要logn轮就可以完成排序。
      快速排序的思想是:每趟排序时选出一个基准值,然后将所有元素与该基准值比较,并按大小分成左右两堆,然后递归执行该过程,直到所有元素都完成排序。
      快速排序的步骤如下:

    1>先从数列中取出一个数作为基准数。
    2>分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
    3>再对左右区间重复第二步,直到各区间只有一个数。

      快排的不同版本,演进过程示例:

    	public static void quickSort1(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		process1(arr, 0, arr.length - 1);
    	}
    
    	//第一版快排,这一版的时间复杂度为O(n2)
    	public static void process1(int[] arr, int L, int R) {
    		if (L >= R) {
    			return;
    		}
    		//在[L,R]范围上,根据arr[R],模仿netherlandsFlag方法,
    		//将数组分为三个部分:<=arr[R]的部分,arr[R]本身,>=
    		//arr[R]的部分,这样确定了在最终的数组中arr[R]的位置,
    		//并返回这个位置
    		int M = partition(arr, L, R);
    		//接下来只要在左右两侧重复这个过程就行
    		process1(arr, L, M - 1);
    		process1(arr, M + 1, R);
    	}
    
    	public static int partition(int[] arr, int L, int R) {
    		if (L > R) {
    			return -1;
    		}
    		if (L == R) {
    			return L;
    		}
    		int lessEqual = L - 1;
    		int index = L;
    		while (index < R) {
    			if (arr[index] <= arr[R]) {
    				swap(arr, index, ++lessEqual);
    			}
    			index++;
    		}
    		swap(arr, ++lessEqual, R);
    		return lessEqual;
    	}
    
    	
    	public static void quickSort2(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		process2(arr, 0, arr.length - 1);
    	}
    
    	//第二版快排:相比第一版的区别/优势:在于一次可以确定
    	//相等基准值的一个区域,而不再只是一个值
    	//第二版的时间复杂度为O(n2)
    	public static void process2(int[] arr, int L, int R) {
    		if (L >= R) {
    			return;
    		}
    		int[] equalArea = netherlandsFlag(arr, L, R);
    		process2(arr, L, equalArea[0] - 1);
    		process2(arr, equalArea[1] + 1, R);
    	}
    	
    	//这个方法的目的是按arr[R]为基准值,将arr数组划分为小于基准值、
    	//等于基准值、大于基准值三个区域
    	
    	//在arr[L...R]上,以arr[R]做基准值,在[L...R]范围内,<arr[R]的数
    	//都放在左侧,=arr[R]的数放在中间,>arr[R]的数放在右边
    	//返回的值为和arr[R]相等的范围的数组
    	public static int[] netherlandsFlag(int[] arr, int L, int R) {
    		if (L > R) {
    			return new int[] { -1, -1 };
    		}
    		if (L == R) {
    			return new int[] { L, R };
    		}
    		//小于基准值的区域的右边界
    		int less = L - 1;
    		//大于基准值的区域的左边界
    		int more = R;
    		int index = L;
    		while (index < more) {
    			//等于基准值,不做处理,判断下一个数据
    			if (arr[index] == arr[R]) {
    				index++;
    			//当前数小于基准值
    			} else if (arr[index] < arr[R]) {
    				//将当前值和小于区域右边的一个值交换:swap
    				//判断下一个数据:index++
    				//小于区域右移:++less(先++是为了完成swap)
    				swap(arr, index++, ++less);
    			} else {
    				//将当前值和大于区域左边的一个值交换:swap
    				//大于区域左移:--more(先--是为了完成swap)
    				swap(arr, index, --more);
    			}
    		}
    		//因为最开始是把arr[R]作为基准值的,所以在进行接下来的一步之前,
    		//arr[R]实际是在大于区域的最右侧的,所以还需要进行一步交换,这样
    		//整个数组就成了小于区域、等于区域、大于区域的样子
    		swap(arr, more, R);
    		//less + 1是等于区域的起始位置,more经过上一步的和arr[R]交换后,
    		//就成了等于区域的结束位置
    		return new int[] { less + 1, more };
    	}
    	
    
    	public static void quickSort3(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		process3(arr, 0, arr.length - 1);
    	}
    
    	//第三版快排:不再固定去arr[R],改为去随机位置的值,然后
    	//和arr[R]进行交换,接下来的过程就和第二版一样
    	
    	//第三版的复杂度变化了,是O(nlogn),该事件复杂度是最终求
    	//的是数学上的一个平均期望值
    	public static void process3(int[] arr, int L, int R) {
    		if (L >= R) {
    			return;
    		}
    		swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    		int[] equalArea = netherlandsFlag(arr, L, R);
    		process3(arr, L, equalArea[0] - 1);
    		process3(arr, equalArea[1] + 1, R);
    	}
    
    	public static void swap(int[] arr, int i, int j) {
    		int tmp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = tmp;
    	}
    

      在选择基准值的时候,越靠近中间,性能越好;越靠近两边,性能越差。第三版随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件。把每一种情况都列出来,会有每种情况下的时间复杂度,但概率都是1/N。那么所有情况都考虑,时间复杂度就是这种概率模型下的长期期望。
      时间复杂度O(N*logN),额外空间复杂度O(logN)都是这么来的。

    4.2 快速排序优化

    4.2.1 三数取中

      该方法指的是选取基准值时,不再取固定位置(如第一个元素、最后一个元素)的值,因为这种固定取值的方式在面对随机输入的数组时,效率是非常高的。但是一旦输入数据是有序的,使用固定位置取值,效率就会非常低。因此此时引入了三数取中,即在数组中随机选出三个元素,然后取三者的中间值做为基准值。

    4.2.2 插入排序

      当待排序序列的长度分割到一定大小(如 < 10)后,使用插入排序。

    4.2.3 相等元素聚集(上个小节中的第二版快排)

      在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割。

    4.3 快速排序的稳定性、复杂度和适用场景

    4.3.1 稳定性

      在使用快速排序时,每次元素分堆都要选择基准因子。此时,基准因子两边都有可能出现和基准因子相同的元素,如序列[1,3,2,4,3,4,6,3],如果选择了array[4]作为基准因子,那么array[1]和array[7]势必会被分到基准因子的同一侧,序列的稳定性被破坏。所以,快速排序是一种不稳定的排序算法。

    4.3.2 时间复杂度

      快速排序的时间复杂度是O(nlogn)【上小节第三版的时间复杂度】。

    4.3.3 适用场景

      快速排序的适用场景是:待排序序列元素较多,并且元素较无序。

    五、希尔排序

    5.1 希尔排序基础

      希尔排序又称为缩小增量排序,是对之前介绍的插入排序的一种优化版本,优化的地方在于:不用每次插入一个元素时,就和序列中有序部分中的所有元素进行比较。
      该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于序列元素总数)作为间隔,所有距离为increment的元素放在同一个逻辑数组中,在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔increment,重复上述逻辑数组划分和排序工作。直到最后取increment=1,将所有元素放在同一个数组中排序为止。
      其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤:
       1>选increment,划分逻辑分组,组内进行直接插入排序。
       2>不断缩小increment,继续组内进行插入排序。
       3>直到increment=1,在包含所有元素的序列内进行直接插入排序。

    5.1.1 排序过程图示

      1>假如有[5,2,3,9,4,7]六个元素,第一趟取increment的方法是:6/3向下取整+1=3。将整个数据列划分为间隔为3的3个逻辑分组,然后对每一个逻辑分组执行直接插入排序,相当于对整个数组执行了部分排序调整。

      2>第二趟将间隔increment= increment/3向下取整+1=2,将整个数组划分为2个间隔为2的逻辑分组,分别进行排序。

      3>第3趟继续缩小间隔。间隔缩小为increment= increment/3向下取整+1=1,当增量为1的时候,实际上就是把整个数列作为一个逻辑分组进行插入排序。

    5.1.2 排序过程实现

      上述图示对应的代码实现,示例如下:

    		/*初始化划分增量*/
    		int increment = len;	
    		int temp;
    		/*每次减小增量,直到increment = 1*/
    		while (increment > 1){	
    			/*增量的取法之一:除三向下取整+1*/
    			increment = increment/3 + 1;
    			/*对每个按增量划分后的逻辑分组,进行直接插入排序*/
    			for (int i = increment; i < len; ++i) {	
    				if (arr[i-increment] > arr[i]) {
    					temp = arr[i];
    					int j = i-increment;
    					/*移动元素并寻找位置*/
    					while (j >= 0 && arr[j] > temp) {	
    						arr[j+increment] = arr[j];
    						j -= increment;
    					} 
    					/*插入元素*/
    					arr[j+increment] = temp;	
    				}
    			}
    		} 
    

      从上述代码可以看出,希尔排序的代码与直接插入排序的代码十分相似。因为希尔排序本就是直接插入排序的优化版本,不同的地方就是间隔慢慢减成1,直接插入排序的间隔一直就是1。

    5.2 希尔排序优化

      由于希尔排序是基于插入排序的,所以在插入排序中也可运用直接插入排序中的优化方式,此处以二分折中的方式来优化希尔排序,示例代码如下:

    	   /*初始化划分增量*/
    	   int increment = len;	
    	   int j,temp,low,mid,high;
    	   /*每次减小增量,直到increment = 1*/
    	   while (increment > 1){	
    		  /*增量的取法之一:除三向下取整+1*/
    		  increment = increment/3 + 1;
    		  /*对每个按增量划分后的逻辑分组,进行直接插入排序*/
    		  for (int i = increment; i < len; ++i) {	
    			 low = 0;
    			 high = i-1;
    			 temp = arr[i];
    	         while(low <= high){
    	            mid = (low+high)/2;
    	            if(arr[mid]>temp){
    	                high = mid-1;
    	            }else{
    	                low = mid+1;
    	            }
    	         }
    	         j = i-increment;
    		     /*移动元素并寻找位置*/
    			 while(j >= high+1){	
    				arr[j+increment] = arr[j];
    				j -= increment;
    			 } 
    			 /*插入元素*/
    			 arr[j+increment] = temp;	
    		  }
    	   }
    

    5.3 希尔排序的稳定性、复杂度及适用场景

    5.3.1 稳定性

      希尔排序是直接插入排序的优化版,在排序过程中,会根据间隔将一个序列划分为不同的逻辑分组,在不同的逻辑分组中,有可能将相同元素的相对位置改变。如[2,2,4,1],按间隔为2,降序排序,前两个元素的相对位置就会改变。因此,希尔排序是不稳定的排序方式。

    5.3.2 时间复杂度

      希尔排序在最坏情况下的时间复杂度为O(n2),平均情况下的时间复杂度为O(n1.3)。

    5.3.3 适用场景

      待排序序列元素较少时。

    展开全文
  • 《糊涂算法》之八大排序——选择排序

    万次阅读 热门讨论 2021-09-26 18:36:32
    选择排序
  • 选择排序 图示过程如下:
  • 排序 - 选择排序

    千次阅读 2021-10-15 15:48:50
    选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。 二、算法步骤 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 再从...
  • Python 选择排序

    万次阅读 2019-11-27 20:07:59
    Python 选择排序 基本原理: 从剩余待排序的数组中选择最小的数和待排序的数做对比。 时间复杂度为O(n^2),n为数组的个数。 空间复杂度为O(1)。 不稳定算法。 该图片来源于网络 选择排序 def select_sort(array): ...
  • 排序算法-之选择排序(直接选择排序,堆排序)   一、排序算法分为:  1.插入排序(直接插入排序&希尔排序)  2.选择排序(直接选择排序&堆排序)  3.交换排序(冒泡排序&快速排序)  4.归并...
  • 排序算法--选择排序--详解及代码

    万次阅读 多人点赞 2019-07-31 21:46:30
    选择排序选择排序( Selection sort)是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 ...
  • 一、简单选择排序。 1、介绍。 在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最小...
  • 选择类:简单选择排序、堆排序 归并类:二路归并排序 基数类:多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下: 本文放出选择算法的两种排序算法代码。 简单选择排序 void SelectSort(int R[], ...
  • 选择排序法和冒泡排序法

    万次阅读 多人点赞 2020-05-21 17:00:57
    选择排序法和冒泡排序法 1.选择排序法 #include<stdio.h> int main() { void sort(int a[],int n); int i,a[10]; printf("please input the original array:"); for(i=0;i<10;i++) scanf("%d",&a...
  • 选择排序算法

    千次阅读 2021-05-09 10:10:00
      选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,...
  • C语言排序(冒泡排序、选择排序、插入排序和快速排序)C语言排序什么是排序?1.冒泡排序基本思想主要思路:动态示例demo2.选择排序基本思想主要思路动态示例demo3.插入排序基本思想主要思路动态示例demo4.快速排序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 882,125
精华内容 352,850
关键字:

选择排序