算法小白--1.排序算法

雨点打透心脏的1/2处 2022-01-23 14:59 239阅读 0赞

### 文章目录 ###

*   *  一、十大排序算法分类及对比
     *  二、各算法原理及实现
     *   *  1.快速排序（Quick Sort）

## 一、十大排序算法分类及对比 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70]  
**稳定**：排序前a位于b前，且a=b，排序完后a仍然位于b前。  
**不稳定**：排序前a位于b前，且a=b，排序完后a可能位于b后。  
**内排序**：所有排序操作都在内存中完成；  
**外排序**：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；  
**时间复杂度**： 一个算法执行所耗费的时间。  
**空间复杂度**：运行完一个程序所需内存的大小。  
**n**:数据规模  
**k**：“桶”的个数

## 二、各算法原理及实现 ##

### 1.快速排序（Quick Sort） ###

**基本思想**：选取一个记录作为基准，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于基准，另一部分都大于基准。然后继续对这两部分继续进行排序，直到整个序列达到有序，这是典型的分治思想。  
**步骤**：(1)从数列中挑出一个元素，称为 “基准”（pivot）；  
(2)重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；  
(3)递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20190604231820846.png]  
![在这里插入图片描述][20190604231919880.png]  
此时50左边都比基准小，右边都比基准大，完成了第一趟排序。  
然后递归地对左右两部分进行排序，直到全部有序。

**代码实现**：

package com.qcby.test;
    
    /** * 快速排序算法 */
    public class QuickSort { 
    	
        public static void main(String[] args) { 
            int data[] = { 50,46,78,32,6,10,2,90,65,46};
            quickSort(data, 0, data.length-1);
        }
    
        private static void quickSort(int[] data, int left, int right){ 
            int base = data[left];
            int leftIndex = left; // 记录当前左边要找的位置
            int rightIndex = right; // 记录当前右边要找的位置
            while(leftIndex < rightIndex){ 
                // 从队列后面往前找出比base小的第一个数， 没有满足条件的则右边下标前移，继续判断
                while(leftIndex < rightIndex && data[rightIndex]>=base){ 
                    rightIndex --;
                }
                // 表示已找到 
                if (leftIndex < rightIndex){ 
                    swap(data, leftIndex, rightIndex);
                    leftIndex ++;
                    print(data);
                }
                // 从队列前面往后找出比base 大的第一个数
                while (leftIndex < rightIndex && data[leftIndex] <= base) { 
                    leftIndex++;
                }
           
                if(leftIndex < rightIndex){ 
                    swap(data, leftIndex, rightIndex);
                    rightIndex --;
                    print(data);
                }
            }
     
            // 以基准数分为2部分, 前后部分递归排序
            if(leftIndex > left){ 
                quickSort(data, left, leftIndex-1);
            }
    
            if(rightIndex < right){ 
                quickSort(data, leftIndex+1, right);
            }
        }
    
        /** * 对换数据位置 * @param data * @param leftIndex * @param rightIndex */
        private static void swap(int[] data, int leftIndex, int rightIndex) { 
            int temp = data[rightIndex];
            data[rightIndex] = data[leftIndex];
            data[leftIndex] = temp;
        }
    
        private static void print(int[] data){ 
            for(int i=0,len = data.length; i<len; i++){ 
                System.out.print(data[i]+" ");
            }
            System.out.println();
        }
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70 2]  
**性能分析**：  
快速排序的最好的情况（每次数据划分得很均匀）时间复杂度为O（nlogn），最坏的情况（需排序的数据为正序或逆序排列时）复杂度为O（n^2）。

> 参考：[https://blog.csdn.net/wq\_1995/article/details/81937926][https_blog.csdn.net_wq_1995_article_details_81937926]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70]: /images/20220123/1af6cd95f93c4767ae9a4bfc318dcfde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70 1]: /images/20220123/ae66e31c96714e58a8aaa636472c427a.png
[20190604231820846.png]: /images/20220123/9aeb38520e184c55852d4477384be1ae.png
[20190604231919880.png]: /images/20220123/ea3cc6d1800a404d937aef004db914fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTcwMjMx_size_16_color_FFFFFF_t_70 2]: /images/20220123/c9573078be59415a8df3c3ae9e4495e6.png
[https_blog.csdn.net_wq_1995_article_details_81937926]: https://blog.csdn.net/wq_1995/article/details/81937926