常用排序算法(二)选择排序、快速排序

小咪咪 2022-05-15 23:41 153阅读 0赞

# [常用排序算法(一)插入排序、希尔排序、冒泡排序][Link 1] #

# [常用排序算法(三)归并排序、堆排序、基数排序][Link 2] #

# 1 选择排序 #

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。算法平均时间复杂度O(n2)。

![70][]

一种用C++实现的选择排序算法如下：

void SelectSort(int a[], int n) 
    {
    	for (int i = 0; i < n - 1 ; i++)
    	{
    		for (int j = i + 1 ; j < n; j++)
    		{
    			if (a[j] < a[i])
    			{
    				int min = a[j];
    				a[j] = a[i];
    				a[i] = min;
    			}
    		}
    	}
    }

上面示例代码中，第二层循环需要找出从下标 i 开始的最小值，对于每一个比a\[i\]小的值a\[j\]都进行交换，下面进行改进：

void SelectSort(int a[],int n) //选择排序
    {
        int mix,temp;
        for(int i=0;i<n-1;i++) //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的
        {
            mix=i; //假设最小元素的下标
            for(int j=i+1;j<n;j++) //将上面假设的最小元素与数组比较，交换出最小的元素的下标
                if(a[j]<a[mix])
                    mix=j;
            //若数组中真的有比假设的元素还小，就交换
            if(i!=mix)
            {
                temp=a[i];
                a[i]=a[mix];
                a[mix]=temp;
            }
        }
    }

改进后的代码，内层循环只进行判断，并记录下最小值的下标，然后在外层循环只需交换一次数据，稍微加快了速度。

注意选择排序与[冒泡排序][Link 1]的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

# 2 快速排序 #

1.  **基本思想：（分治）**
    
     *  先从数列中取出一个数作为key值；
     *  将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
     *  对左右两个小数列重复第二步，直至各区间只有1个数。
2.  **辅助理解：[挖坑填数][Link 3]**
    
     *  初始时 i = 0; j = 9; key=72  
        由于已经将a\[0\]中的数保存到key中，可以理解成在数组a\[0\]上挖了个坑，可以将其它数据填充到这来。  
        从j开始向前找一个比key小的数。当j=8，符合条件，**a\[0\] = a\[8\] ; i++ ;** 将a\[8\]挖出再填到上一个坑a\[0\]中。  
        这样一个坑a\[0\]就被搞定了，但又形成了一个新坑a\[8\]，这怎么办了？简单，再找数字来填a\[8\]这个坑。  
        这次从i开始向后找一个大于key的数，当i=3，符合条件，**a\[8\] = a\[3\] ; j-- ;** 将a\[3\]挖出再填到上一个坑中。
        
            数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
             0   1   2    3    4    5    6    7    8    9
     *  此时 i = 3; j = 7; key=72  
        再重复上面的步骤，先从后向前找，再从前向后找。  
        从j开始向前找，当j=5，符合条件，将a\[5\]挖出填到上一个坑中，**a\[3\] = a\[5\]; i++;**  
        从i开始向后找，当i=5时，由于i==j退出。  
        此时，i = j = 5，而a\[5\]刚好又是上次挖的坑，因此将key填入a\[5\]。
        
            数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
             0   1   2    3    4    5    6    7    8    9
     *  可以看出a\[5\]前面的数字都小于它，a\[5\]后面的数字都大于它。因此再对a\[0…4\]和a\[6…9\]这二个子区间重复上述步骤就可以了。
        
            <数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
             0   1   2    3    4    5    6    7    8    9

**平均时间复杂度：**O(N\*logN)

void QuickSort(int a[], int l, int r) {
    	if (l >= r)
    		return;
    
    	int i = l; int j = r; int key = a[l];//选择第一个数为key
    
    	while (i<j) {
    
    		while (i<j && a[j] >= key)//从右向左找第一个小于key的值
    			j--;
    		if (i<j) {
    			a[i] = a[j];
    			i++;
    		}
    
    		while (i<j && a[i]<key)//从左向右找第一个大于key的值
    			i++;
    
    		if (i<j) {
    			a[j] = a[i];
    			j--;
    		}
    	}
    	a[i] = key;
    	QuickSort(a, l, i - 1);//递归调用
    	QuickSort(a, i + 1, r);//递归调用
    }

[Link 1]: https://blog.csdn.net/u010183728/article/details/81348339
[Link 2]: https://blog.csdn.net/u010183728/article/details/81711194
[70]: /images/20220516/ae59a07bfa0e4fa6938a3c160a4f4b65.png
[Link 3]: http://blog.csdn.net/morewindows/article/details/6684558