十大经典排序算法总结（含Java代码实现）

2.3 代码实现

/** 
 * 选择排序 
 * @param array 
 * @return 
 */ 
 public static int[] selectionSort(int[] array) { 
 if (array.length == 0) 
 return array; 
 for (int i = 0; i < array.length; i++) { 
 int minIndex = i; 
 for (int j = i; j < array.length; j++) { 
 if (array[j] < array[minIndex]) //找到最小的数 
 minIndex = j; //将最小数的索引保存 
 } 
 int temp = array[minIndex]; 
 array[minIndex] = array[i]; 
 array[i] = temp; 
 } 
 return array; 
 } 

2.4 算法分析

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序(即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。插入排序：直接插入排序

3.1 算法描述

• 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
• 从第一个元素开始，该元素可以认为已经被排序;
• 取出下一个元素，在已经排序的元素序列中从后向前扫描;
• 如果该元素(已排序)大于新元素，将该元素移到下一位置;
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置;
• 将新元素插入到该位置后;
• 重复步骤2~5。

3.2 动图演示

3.2 代码实现

/** 
 * 插入排序 
 * @param array 
 * @return 
 */ 
 public static int[] insertionSort(int[] array) { 
 if (array.length == 0) 
 return array; 
 int current; 
 for (int i = 0; i < array.length - 1; i++) { 
 current = array[i + 1]; 
 int preIndex = i; 
 while (preIndex >= 0 && current < array[preIndex]) { 
 array[preIndex + 1] = array[preIndex]; 
 preIndex--; 
 } 
 array[preIndex + 1] = current; 
 } 
 return array; 
 } 

3.4 算法分析

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

4、希尔排序(Shell Sort)

（编辑：西安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!