精华内容
下载资源
问答
  • 每次从未排序序列中拿一个元素,接着找到这个元素在已排序中可以插入的位置后插入,然后从未排序序列中将这个元素删除,这就完成了一个元素的排序。类似于我们抓扑克牌,手上的牌都拍好了序,桌上的拍没有排好序,...

    插入排序

    插入排序将序列分成已排序未排序两部分。每次从未排序序列中拿一个元素,接着找到这个元素在已排序中可以插入的位置后插入,然后从未排序序列中将这个元素删除,这就完成了一个元素的排序。类似于我们抓扑克牌,手上的牌都拍好了序,桌上的拍没有排好序,每次我们从桌上抓取一张牌插入到手上的牌中。重复这个过程,我们就可以得到一个排好序的序列。
    在这里插入图片描述
    下面我们使用代码来实现插入排序。

    /*
    	 	思路:
    	 		1. 从未排序的序列中拿取元素ele
    	 		2. 在已排序的序列中找到元素ele的插入位置
    	 		3. 在找到的位置中插入元素ele
    	 		4. 重复上述直到未排序的序列中没有元素
    	 */
    	@Test
    	public void insertSort() { 
    		int[] arr = { 1, 23, 41, 231, 31, 5, 4, 2, 67 };
    		for (int i = 1; i < arr.length; i++) { // 控制插入的数字为第几个
    			int temp = arr[i];	// 需要插入的元素
    			int index = i - 1;	// 记录temp在已排好序的位置
    			// 寻找插入位置
    			while(index >= 0 && temp<arr[index]) {	// 找位置
    				// 将元素往后移动一个位置,为temp腾出插入空间
    				arr[index+1] = arr[index];
    				index--;
    			}
    			arr[index+1] = temp;	// 插入
    		}
    	}
    

    上述的for循环中,arr[0 … i] 总是保存已经排好序的序列,而arr[i+1 … arr.length-1]总是保存着未排序的序列,我们把这种性质称为循环不变式,下面我们先介绍循环不变式。


    循环不变式

    循环不变式主要帮助我们来理解算法的正确性,关于循环不变式总是有三条性质需要我们证明

    • 初始化
        循环的第一次迭代之前,它为真
    • 保持
        如果循环的某次迭代之前它为真,那么下一次迭代它也为真
    • 终止
        在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的。

    在插入排序中,初始化arr[0 … i] 中只有一个元素,并已经排好序,arr[i+1 … arr.length - 1] 有a.length -1 个元素,且无序。循环体内的代码为我们保持初始化的中的特性,当i = arr.length时,循环终止。
    插入排序的最坏情况下的时间复杂度为O(n2)O(n^2),外层循环循环n次,里层循环n次。


    希尔排序

    希尔排序源自于Donald Shell,希尔排序是通过比较一定间隔的元素来进行排序的,每一趟比较所用的距离随着算法的进行而缩小,直到只比较相邻元素的下一趟排序为止,因为这个原因希尔排序也叫缩减增量排序。希尔排序中影响排序性能的可控变量是**增量序列(如序列h1,h2,h3…ht,其中h1等于1)**的选择,合适的增量序列能够提高性能。Shell建议的增量序列是ht = N/2 、hk = hk+1/2。下面给出进行一次希尔排序
    在这里插入图片描述
    下面是希尔排序的代码实现

    	@Test
    	public void shellSort1() {
    		int[] arr = {12,32,123,42,121,41,56,72,45};
    		for(int gap = arr.length/2 ; gap > 0 ; gap /=2) {// 计算增量序列,终止条件gap=0
    			for(int i = gap ; i < arr.length; i++) { // 从index = gap开始逐渐比较
    				int temp = arr[i];	// 保存gap的值,下面可能会被覆盖
    				int index; // 保存temp应该放置的为止
    				// 间隔比较,满足条件则交换
    				for(index = i ; index >= gap && temp < arr[index-gap] ; index-=gap) {	
    					arr[index] = arr[index-gap];
    				}
    				arr[index] = temp;	// 将temp放到对于的为止
    			}
    		}
    	}
    

    每次循环后都有arr[i]arr[i+gap]arr[i+gap+gap]...arr[i] \leq arr[i+gap] \leq arr[i+gap+gap] \leq ...,这是循环中不变的量,希尔排序的时间复杂度在最坏情况下为O(n2)O(n^2)


    归并排序

    分治法

    介绍归并排序前,我们先引入一个算法的设计方法——分治法
    有许多算法在结构上是递归的,为了解决一个问题,我们将这个问题拆分成更小的问题,为了解决这个更小的问题,我们又将其拆分,递归求解这些子问题,然后在合并这些问题的解来建立原来问题的解。分治模式在每层递归都有三个步骤:

    • 分解
        将原问题分解成若干子问题,这些问题是原问题规模较小的子问题
    • 解决
        递归求解子问题,如果子问题足够小,则直接求解
    • 合并
        合并子问题的解成为原问题的解

    这种方法在二叉堆和优先队列中使用过,建堆的时候递归建立子堆。在接下来我们要介绍的归并排序中也使用了这种方法。

    现在我们把注意力放到归并排序上,归并排序将序列分解成两个子序列,然后将这子序列合并,合并之前递归使用归并排序排列两个子序列

    • 分解
        分解待排序的n个元素的序列分解成两个有n/2个元素的子序列
    • 解决
        使用归并排序递归排序元素大于1的子序列
    • 合并
        合并两个已排序的子序列以产生已排序的答案
      在这里插入图片描述

    下面给出使用分治法来分解递归排序的代码

    public static void mergeSort(int[] arr) {
    		mergeSort(arr,0,arr.length-1);
    	}
    	
    private static void mergeSort(int[] arr,int start,int end) {
    		if(start < end) {
    			// 选取主元
    			int center = (start + end)/2;
    			// 递归求解子序列
    			mergeSort(arr,start,center);
    			mergeSort(arr,center+1,end);
    			// 解决并合并
    			merge(arr,start,center,end);
    		}
    	}
    

    上述代码中我们只是将问题分解,并没有解决和合并,下面的代码才是帮助我们解决并合并,需要注意的是分解成两个序列后,我们维持了对每一个序列都维持了一个游标,这个游标指示序列下一个合并的元素。下面给出具体代码

    private static void merge(int[] arr,int start,int center,int end) {
    		
    		/*
    		 * 	将传过来的数组分解成两个子序列
    		 */
    		int leftSize = center - start + 1;	// 子序列的大小
    		int rightSize = end - center; 
    		
    		int[] leftArr = new int[leftSize];	// 子序列	
    		int[] rightArr = new int[rightSize];
    		
    		for(int i = 0 ; i < leftSize ; i++) {	// 给子序列赋值
    			leftArr[i] = arr[start + i];
    		}
    		for(int i = 0 ; i < rightSize ; i ++) {
    			rightArr[i] = arr[center + i + 1];
    		}
    		
    		/*
    		 * 合并,将leftArr和rightArr数组中的值合并到arr中
    		 * 需要考虑的情况
    		 * 1>leftPos和rightPos必须在范围内
    		 * 2>如果leftPos超过了leftArr.length,则使用rightArr中的元素
    		 * 3>如果rightPos超过了rightPos.length,则使用leftArr中的元素 
    		 */
    		for(int k = start,leftPos = 0,rightPos = 0 ; k <= end ; k++) {
    			if(leftPos < leftArr.length && rightPos < rightArr.length) {
    				if(leftArr[leftPos] <= rightArr[rightPos]) {
    					arr[k] = leftArr[leftPos++];
    				}else {
    					arr[k] = rightArr[rightPos++];
    				}
    			}else if(leftPos < leftArr.length) {
    				arr[k] = leftArr[leftPos++];
    			}else if(rightPos < rightArr.length) {
    				arr[k] = rightArr[rightPos++];
    			}
    		}
    	}
    

    归并排序在最坏情况下的时间复杂度的期望值为O(nlgn)O(nlgn),这比前面的插入排序和希尔排序的性能更好。


    快速排序

    与归并排序一样,快速排序也使用了分治思想。快速排序从序列中选取一个元素作为主元,根据主元将序列分成三个子序列,第一个子序列里面包含小于等于主元的元素,第二个子序列只有主元,第三个子序列里面包含大于主元的元素,然后递归使用快速排序递归排列第一个子序列和第三个子序列中的元素。快速排序中对性能影响较大的是主元的选取,一个合适的主元能够提高性能。下面是快速排序的三步分治过程:

    • 分解
        数组被划分成三个部分,A[p…q-1]、 A[q]、A[q+1 … r],其中有
           A[p...q1]A[q]A[q+1...r]A[p...q-1] \leq A[q] \leq A[q+1 ... r]
    • 解决
        通过递归调用快速排序,对子数组A[p…q-1]和A[q+1 … r]进行排序
    • 合并
        因为子数组都是原址排序(没有借助外部的资源),所以不用合并。
      下面是代码实现
    	public static void quickSort(int[] arr) {
    		quickSort(arr, 0, arr.length - 1);
    	}
    
    	private static void quickSort(int[] arr, int start, int end) {
    		/*
    		 	分治法
    			 	分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列
    			 	解决:递归排序两个子序列
    			 	合并:快速排序不需要合并
    		 */
    		if (start < end) {
    			// 分解
    			int position = partition(arr, start, end);	
    			// 递归解决
    			quickSort(arr, start, position - 1);
    			quickSort(arr, position + 1, end);
    		}
    	}
    

    上诉代码中最重要的是分解partition()这个方法,它实现了对子数组的原址重排。
    下面先给出代码,在代码中我们进行了分析

    	/*
    		 循环不变式
    		 	初始化: 在循环的第一轮迭代开始之前,position=start-1和k=start.
    		 		   因为在position和start之间、position+1和k之间没有值。
    		 	保持:每一次循环都满足arr[0 ... position] <= arr[end] < arr[position+1 ... k]
    		 	终止:当k=end时终止
    	 */
    	private static int partition(int[] arr, int start, int end) {
    
    		int endEle = arr[end]; // 将最后一个当作主元
    
    		int position = start - 1; // 记录下一个主元的位置
    		
    		for (int k = start; k < end; k++) {	// arr[k]存取比endEle大的值
    			
    			if (arr[k] <= endEle) {
    				position++;
    				// 交换
    				if(position < k) {
    					int temp = arr[position];
    					arr[position] = arr[k];
    					arr[k] = temp;
    				}
    			}
    		}
    		position++;
    		if(position != end) { // 若position 和end 相等,则说明endEle为最大值,此时不用交换
    			  int temp = arr[position];
    			  arr[position] = arr[end];
    			  arr[end] = temp;
    		}
    		return position;
    	}
    

    快速排序在最坏情况下的时间复杂度为O(n2)O(n^2),虽然最坏情况时间复杂度很差,但是快速排序通常是实际排序应用中的最好选择,因为它的平均性能非常好,它的期望时间复杂度是O(nlgn)O(nlgn)

    展开全文
  • 排序算法

    2018-05-08 21:26:31
    首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。 代码实现 public static int[] selectionSort(int...

    选择排序

    • 实现原理

    首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。

    • 代码实现
    public static int[] selectionSort(int[] arr){
            if (null == arr || arr.length == 0){
                return null;
            }
            int length = arr.length;
            for (int i = 0; i < length - 1; i++) {
                int min = i;
                for (int j = i + 1; j < length; j++) {
                    if (arr[j] < arr[min]){
                        min = j;
                    }
                }
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            return arr;
        }
    • 案例分析

    时间复杂度与空间复杂度
    每次要找一遍最小值,最坏情况下找n次,这样的过程要执行n次,所以时间复杂度还是O(n^2)。空间复杂度是O(1)。

    快速排序

    • 实现原理

    在数据集之中,选择一个元素作为”基准”(pivot)。
    所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition)。
    操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
    对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
    - 代码实现

    public static int partition(int[] array, int lo, int hi) {
                // 固定的切分方式
                int key = array[lo];
                while (lo < hi) {
                    while (array[hi] >= key && hi > lo) {// 从后半部分向前扫描
                            hi--;
                    }
                    array[lo] = array[hi];
                    while (array[lo] <= key && hi > lo) {// 从前半部分向后扫描
                        lo++;
                    }
                    array[hi] = array[lo];
                }
                array[hi] = key;
                return hi;
            }
    
            public static int[] sort(int[] array, int lo, int hi) {
                if (lo >= hi) {
                    return array;
                }
                int index = partition(array, lo, hi);
                sort(array, lo, index - 1);
                sort(array, index + 1, hi);
                return array;
    • 案例分析

    时间复杂度与空间复杂度
    快速排序也是一个不稳定排序,平均时间复杂度是O(nlogn)。空间复杂度是O(logn)。

    冒泡排序

    • 实现原理

    依次比较相邻的两个元素,如果第一个元素大于第二个元素就交换它们的位置。这样比较一轮之后,最大的元素就会跑到队尾。然后对未排序的序列重复这个过程,最终转换成有序序列。

    • 代码实现
    public static int[] bubbleSort(int[] arr){
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - i -1; j++) {
                    if (arr[j] > arr[j + 1]){
                        arr[j] = arr[j] + arr[j + 1];
                        arr[j + 1] = arr[j] - arr[j + 1];
                        arr[j] = arr[j] - arr[j + 1];
                    }
                }
            }
            return arr;
        }
    • 时间复杂度与空间复杂度

    由于我们要重复执行n次冒泡,每次冒泡要执行n次比较(实际是1到n的等差数列,也就是(a1 + an) * n / 2),也就是 O(n^2)。 空间复杂度是O(1)。

    插入排序

    • 实现原理

    认为第一个元素是排好序的,从第二个开始遍历。
    拿出当前元素的值,从排好序的序列中从后往前找。
    如果序列中的元素比当前元素大,就把它后移。直到找到一个小的。
    把当前元素放在这个小的后面(后面的比当前大,它已经被后移了)。
    - 代码实现

    public static int[] insertionSort(int[] arr){
            for (int i = 1; i < arr.length; i++) {
                for (int j = i; j > 0; j--) {
                    if (arr[j] < arr[j - 1]){
                        int temp = arr[j];
                        arr[j] = arr[j - 1];
                        arr[j - 1] = temp;
                    }
                }
            }
            return arr;
        }
    • 时间复杂度与空间复杂度

    因为要选择n次,而且插入时最坏要比较n次,所以时间复杂度同样是O(n^2)。空间复杂度是O(1)。

    希尔排序

    • 实现原理

    先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
    然后取 d2(d2 < d1)
    重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。
    - 代码实现

    public static int[] shellSort(int[] arr){
            for (int gap = arr.length/2; gap > 0 ; gap/=2) {
                for (int i = gap; i < arr.length; i++) {
                    int j = i;
                    while (j-gap>=0 && arr[j] < arr[j-gap]){
                        int temp = arr[j];
                        arr[j] = arr[j-gap];
                        arr[j-gap] = temp;
                        j -= gap;
                    }
                }
            }
            return arr;
        }
    • 时间复杂度与空间复杂度

    希尔排序的时间复杂度受步长的影响,平均时间复杂度是O(n log2 n),空间复杂度是O(1)。

    归并排序

    • 实现原理

    把 n 个记录看成 n 个长度为 l 的有序子表
    进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表
    重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
    总而言之,归并排序就是使用递归,先分解数组为子数组,再合并数组。

    • 代码实现
    public static int[] mergeSort(int[] arr){
            int[] temp =new int[arr.length];
            internalMergeSort(arr, temp, 0, arr.length-1);
            return temp;
        }
        private static void internalMergeSort(int[] a, int[] b, int left, int right){
            //当left==right的时,已经不需要再划分了
            if (left<right){
                int middle = (left+right)/2;
                internalMergeSort(a, b, left, middle);          //左子数组
                internalMergeSort(a, b, middle+1, right);       //右子数组
                mergeSortedArray(a, b, left, middle, right);    //合并两个子数组
            }
        }
        // 合并两个有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]。temp是辅助数组。
        private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
            int i=left;
            int j=middle+1;
            int k=0;
            while ( i<=middle && j<=right){
                if (arr[i] <=arr[j]){
                    temp[k++] = arr[i++];
                }
                else{
                    temp[k++] = arr[j++];
                }
            }
            while (i <=middle){
                temp[k++] = arr[i++];
            }
            while ( j<=right){
                temp[k++] = arr[j++];
            }
            //把数据复制回原数组
            for (i=0; i<k; ++i){
                arr[left+i] = temp[i];
            }
        }
    • 案例分析

    案例1

    以数组 array = [4 2 8 3 5 1 7 6] 为例,首先将数组分为长度为 2 的子数组,并使每个子数组有序:

    [4 2] [8 3] [5 1] [7 6] ↓

    [2 4] [3 8] [1 5] [6 7]

    然后再两两合并:

    [2 4 3 8] [1 5 6 7] ↓

    [2 3 4 8] [1 5 6 7]

    最后将两个子数组合并:

    [2 3 4 8 1 5 6 7] ↓

    [1 2 3 4 5 6 7 8]

    • 时间复杂度与空间复杂度

    在合并数组过程中,实际的操作是当前两个子数组的长度,即2m。又因为打散数组是二分的,最终循环执行数是logn。所以这个算法最终时间复杂度是O(nlogn),空间复杂度是O(1)。

    堆排序

    • 实现原理

    堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

    最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
    创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
    堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

    Parent(i) = floor((i-1)/2),i 的父节点下标
    Left(i) = 2i + 1,i 的左子节点下标
    Right(i) = 2(i + 1),i 的右子节点下标
    - 代码实现

    /**
         * 堆排序
         */
        public static int[] heapSort(int[] arr) {
            // 将待排序的序列构建成一个大顶堆
            for (int i = arr.length / 2; i >= 0; i--){
                heapAdjust(arr, i, arr.length);
            }
    
            // 逐步将每个最大值的根节点与末尾元素交换,并且再调整二叉树,使其成为大顶堆
            for (int i = arr.length - 1; i > 0; i--) {
                swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
                heapAdjust(arr, 0, i); // 交换之后,需要重新检查堆是否符合大顶堆,不符合则要调整
            }
            return arr;
        }
    
        /**
         * 构建堆的过程
         * @param arr 需要排序的数组
         * @param i 需要构建堆的根节点的序号
         * @param n 数组的长度
         */
        private static void heapAdjust(int[] arr, int i, int n) {
            int child;
            int father;
            for (father = arr[i]; leftChild(i) < n; i = child) {
                child = leftChild(i);
    
                // 如果左子树小于右子树,则需要比较右子树和父节点
                if (child != n - 1 && arr[child] < arr[child + 1]) {
                    child++; // 序号增1,指向右子树
                }
    
                // 如果父节点小于孩子结点,则需要交换
                if (father < arr[child]) {
                    arr[i] = arr[child];
                } else {
                    break; // 大顶堆结构未被破坏,不需要调整
                }
            }
            arr[i] = father;
        }
    
        // 获取到左孩子结点
        private static int leftChild(int i) {
            return 2 * i + 1;
        }
    
        // 交换元素位置
        private static void swap(int[] arr, int index1, int index2) {
            int tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
    • 时间复杂度与空间复杂度

    堆执行一次调整需要O(logn)的时间,在排序过程中需要遍历所有元素执行堆调整,所以最终时间复杂度是O(nlogn)。空间复杂度是O(1)。

    展开全文
  • 相同点 三者都是简单直观容易理解的排序算法。 三者都是通过比较完成排序的。...选择排序每次迭代从未排序序列中选出最大(小)值,放在已排序序列末端。 插入排序每次迭代把未排序序列首段元素插入到已排序序列的...

    相同点
    三者都是简单直观容易理解的排序算法。
    三者都是通过比较完成排序的。
    三者都是构造已排序序列,迭代元素个数次,且保证每次迭代前后已排序序列都是有序的。这样,迭代元素个数次后,排序即完成。
    区别
    区别在于每次迭代保持已排序序列有序的具体过程:
    选择排序每次迭代从未排序序列中选出最大(小)值,放在已排序序列末端。
    插入排序每次迭代把未排序序列首段元素插入到已排序序列的合适位置(即保证插入后已排序序列仍是有序的)。
    冒泡排序每次迭代把未排序序列首段元素从已排序序列末端开始不断交换,直到已排序序列有序。
    冒泡排序其实也属于选择排序
    冒泡排序遍历未排序序列,一旦发现逆序对,便交换,这样,每次遍历,都能把未排序序列中的最大者浮动到末尾。
    (对于基本有序的序列,插入排序快于任何排序(快速排序对基本有序序列效率反而低)。)


    测试:

    #include <stdio.h>
    #include <stdlib.h>
    void swap_my(int *a, int *b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    void select_sort(int *arrInput, int len)//从小到大排序 
    {
    	int mini;
    	for(int i=0;i<len;i++)
    	{
    		mini=i;
    		for(int j=i+1;j<len;j++)
    			 if(arrInput[mini]>arrInput[j])
    			 	mini=j;
     		swap_my(&arrInput[i],&arrInput[mini]);
    	} 
    }
    void bubble_sort(int * arrInput, int len)
    {
    	for(int i=0;i<len;i++)
    	{
    		for(int j=i;j>=1;j--)
    			if(arrInput[j]<arrInput[j-1])
    				swap_my(&arrInput[j],&arrInput[j-1]);
    			else
    				break;
    	}
    }
    void insert_sort(int * arrInput, int len)
    {
    	int temp;
    	for(int i=1;i<len;i++)
    	{
    		temp=arrInput[i];int j;
    		for(j=i-1;j>=0;j--)
    		{
    			if(temp>=arrInput[j])
    			{
    				break;
    			}
    			else
    				arrInput[j+1]=arrInput[j];	
    		}
    		arrInput[j+1]=temp;
    	}
    }
    int main()
    {
    	int len;
    	printf("输入数组长度:");
    	scanf("%d",&len);
    	int *arrNum=(int*)malloc(sizeof(int)*len);
    	for(int z=0;z<len;z++)
    		scanf("%d", &arrNum[z]);
    		
    	insert_sort(arrNum, len);
    	for(int i=0;i<len;i++)
    		printf("%d ", arrNum[i]);
    	printf("\n");
    		insert_sort(arrNum, len);
    	for(int i=0;i<len;i++)
    		printf("%d ", arrNum[i]);
    	printf("\n");
    	insert_sort(arrNum, len);
    	for(int i=0;i<len;i++)
    		printf("%d ", arrNum[i]);
    	printf("\n");
    	return 0;
    }
    
    展开全文
  • 排序算法小结

    2019-02-20 11:38:58
    插入排序:从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列中的正确位置上的排序方法。 交换排序:当每两个元素比较出现逆序时,就相互交换位置的排序方法。 选择排序:从未排序序列中...

    内部排序算法性能小结

      内部排序按排序过程中依据的不同原则,则大致可分为:

    • 插入排序:从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列中的正确位置上的排序方法。
    • 交换排序:当每两个元素比较出现逆序时,就相互交换位置的排序方法。
    • 选择排序:从未排序序列中挑选元素,并将其放入已排序序列的一端的方法。
    • 归并排序:依次将每两个相邻的有序表合并成一个有序表的排序方法。
    • 基数排序:借助多关键字排序的思想对单逻辑关键字进行排序的方法。
      其中插入排序、交换排序、选择排序又分别有不同的排序方法:
      在这里插入图片描述

    各种排序算法所对应的时间复杂度、空间复杂度及排序稳定性如下表:

    排序方法 平均时间 辅助空间 稳定性
    直接插入排序 O(n2n^2) O(1) 稳定
    折半插入排序 O(n2n^2) O(1) 稳定
    希尔排序 O(n1.5n^{1.5}) O(1) 不稳定
    起泡排序 O(n2n^2) O(1) 稳定
    快速排序 O(nlognnlogn) O(lognlogn) 不稳定
    简单选择排序 O(n2n^2) O(1) 不稳定
    堆排序 O(nlognnlogn) O(1) 不稳定
    归并排序 O(nlognnlogn) O(n) 稳定
    基数排序 O(ndnd) O(rd) 稳定

    今天的排序算法小结就先写到这里,有许多不足之处,有待以后改进吧!

    展开全文
  • 选择排序

    2021-02-25 15:14:35
    首先从未排序序列中找出最小(最大)元素,放在序列的起始位置 再从剩余未排序序列中找出最小(最大)元素,放在已排序序列的末尾 重复第二步骤,直到所有元素均排列完毕 举个例子 原始序列:{45, 21,
  • 首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。 代码实现 案例分析 时间复杂度与...
  • 一、基本思想 ...排序过程仍是每次从未排序序列中找到最大元素并放到已排序序列的合适位置。对于有 n 个记录的序列,最多需经过 n-1 轮排序,可使该序列有序。 以序列 12, 23, 33, 8, 99, 0 为例。有 6 ...
  • 首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。 代码实现 案例分析 时间复杂度与
  • 数据结构 作业答案 第8章 排序

    千次阅读 2020-06-14 18:19:25
    (1)从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种排序方法称为( )。 A.归并排序 B.冒泡排序 C.插入排序 D.选择排序 答案:C (2)从未排序序列中...
  • 一、选择排序简介选择...然后,继续从未排序序列中找到最小(大)的元素,存放到已排序序列的末尾。直到所有元素都存放到了已排序序列中,列表排序完成。选择排序每次都是去找最小(大)的元素,隐含了一种挑选的过程,...
  • 一、选择排序简介选择...然后,继续从未排序序列中找到最小(大)的元素,存放到已排序序列的末尾。直到所有元素都存放到了已排序序列中,列表排序完成。选择排序每次都是去找最小(大)的元素,隐含了一种挑选的过程,...
  • 而是每次从未排序序列中找出最大(小)元素,存放到排序序列的末位位置。再从剩下未排序元素中继续寻找最大(小)元素,然后放到未排序序列的末尾。重复第以上步骤,直到所有元素都排序完毕。2.举例采用选择排序算法...
  • 之后每次从未排序序列中取一个元素插入已排序序列,直到未排序序列元素个数为零,排序就完成了。 下面给出代码void InsertionSort(int A[], int n) { /*A[]为待排数组,n为数组中元素个数*/ int temp
  • 数据结构排序习题.pdf

    2020-09-02 10:13:23
    从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较然后将其放在已排序序列 的合适位置该排序方法称为 A 排序法 A 直接插入 B 简单选择 C 希尔 D 二路归并 2. 直接插入排序在最好情况下的时间复杂度...
  • 而是每次从未排序序列中找出最大(小)元素,存放到排序序列的末位位置。再从剩下未排序元素中继续寻找最大(小)元素,然后放到未排序序列的末尾。重复第以上步骤,直到所有元素都排序完毕。2.举例采用选择排序算法...
  • 排序算法 --- 堆排序

    2019-05-01 12:46:30
    然后从未排序 序列中,去 “选择” 一个最小值的元素,把它放到前面已排序的序列中去; 然后不断的重复这个过程。时间复杂度显而易见:O(n2) public class sort { //写一个交换数组中两个元素的方法 pu...
  • 简单选择排序是一种不稳定排序算法,从未排序序列中选择关键字最小的元素与该序列中第一个关键字交换位置,每一趟排序可以确定一个元素的最终位置,空间复杂度:O(1),时间复杂度:O(n²)。 void SimpleSelectSort...
  • 数据结构_练习 第8章 排序

    万次阅读 多人点赞 2018-01-09 00:46:06
    (1)从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种排序方法称为( )。 A.归并排序 B.冒泡排序 C.插入排序 D.选择排序  答案:C (2)从未...
  • 插入排序之所以叫插入排序,是因为它的排序方式是不断从未排序序列中取出一个数,插入到已排序序列的合适位置。就像是数组插入一样,需要不断的移动数据,如果要插入的这个数是在已排序的序列中间的话,就需要从中间...
  • 七种排序算法

    2017-10-26 21:17:56
    实现原理首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。—————————————————code————...
  • 排序算法思想

    2018-12-22 18:49:00
    冒泡排序: ...升序首先在未排序序列中找到最小的,存放在排序序列的起始位,然后再从未排序序列中继续寻找最小的排在以排序列后面。以此类推,直到所有元素均排序完毕。 插入排序 升序 通过构建有...
  • C++选择排序

    2021-02-12 21:02:38
    选择排序法是一个比较直观的排序方法,排序原理为:从未排序序列中选择出最小(大)值放入已排序序列之首,再从剩余元素中选最小值放入已排序序列末端。以此类推,循环n-1次便完成排序。 2.选择排序法的所属类别 选择...
  • 排序学习要点

    2020-11-20 12:46:18
    选择排序是从未排序序列中选出最小记录放在已排序序列的一端;归并排序是将有序序列进行合并,本章知识点的组织结构如下图所示: 重点/难点/要点 本章的重点是: 各种排序算法的基本思想; 各种排序算法的执行过程...
  •   直接插入排序是属于插入排序中的一种简单的排序,它通过抽象两个序列,一个为正在排序的序列称之为有序序列,一个为未排序序列,每次从未排序序列中取值放入有序序列,来完成排序,就像打扑克牌一样 三、直接...
  • 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较然后将其放在已排序序列 的合适位置该排序方法称为 A 排序法 A 直接插入 B 简单选择 C 希尔 D 二路归并 2. 直接插入排序在最好情况下的时间复杂度...
  • 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较然后将其放在已排序序列 的合适位置该排序方法称为 A 排序法 A 直接插入 B 简单选择 C 希尔 D 二路归并 2. 直接插入排序在最好情况下的时间复杂度...
  • 插入排序 Insert Sort

    2019-01-30 12:24:30
    文章目录插入排序1. 基本原理2. 算法步骤3. 动画演示4. 参考实现5. 复杂度分析6....插入排序 1. 基本原理 每步将一个待排序的元素...从未排序序列中取出下一个元素记为 a,在已排序的序列中从后向前扫描 如果该元素(已...
  • 一.基础排序

    2018-11-23 11:10:52
    算法思想:首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。 #include&lt;iostream&gt; using ...
  • 常见七种排序算法

    2017-11-01 14:54:52
    首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。 代码实现 public static int[] selectio

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 206
精华内容 82
关键字:

从未排序序列中