1、冒泡排序- 依次比较相邻两元素若前一元素大于后一元素则交换之直至最后一个元素即为最大然后重新从首元素开始重复同样的操作直至倒数第二个元素即为次大元素依次类推。如同水中的气泡依次将最大或最小元素气泡浮出水面。实现代码就是两个for循环然后比较交换位置。时间复杂度O(N2)2、选择排序- 首先初始化最小元素索引值为首元素依次遍历待排序数列若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置直至遇到尾元素结束一次遍历并将最小索引处元素与首元素交换然后初始化最小索引值为第二个待排序数列元素位置同样的操作可得到数列第二个元素即为次小元素以此类推。简单的说一次遍历找出最小的元素将最小的元素放在最前面第二次就找出第二小的交换第二个位置以此类推。时间复杂度O(N2)3、快速排序- 类似于选择排序的定位思想选一基准元素依次将剩余元素中小于该基准元素的值放置其左侧大于等于该基准元素的值放置其右侧然后取基准元素的前半部分和后半部分分别进行同样的处理以此类推直至各子序列剩余一个元素时即排序完成类比二叉树的思想from up to down时间复杂度O(NlogN)import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] a {1, 2, 4, 5, 7, 4, 5, 3, 9, 0}; System.out.println(Arrays.toString(a)); quickSort(a); System.out.println(Arrays.toString(a)); } public static void quickSort(int[] a) { if (a.length 0) { quickSort(a, 0, a.length - 1); } } private static void quickSort(int[] a, int low, int high) { //1,找到递归算法的出口 if (low high) { return; } //2, 存 int i low; int j high; //3,key int key a[low]; //4完成一趟排序 while (i j) { //4.1 从右往左找到第一个小于key的数 while (i j a[j] key) { j--; } // 4.2 从左往右找到第一个大于key的数 while (i j a[i] key) { i; } //4.3 交换 if (i j) { swap(a,i,j); } } // 4.4调整key的位置 swap(a,i,low); //5, 对key左边的数快排 quickSort(a, low, i - 1); //6, 对key右边的数快排 quickSort(a, i 1, high); } private static void swap(int[] a, int i, int j) { int p a[i]; a[i] a[j]; a[j] p; } }4、插入排序- 数列前面部分看为有序依次将后面的无序数列元素插入到前面的有序数列中初始状态有序数列仅有一个元素即首元素。在将无序数列元素插入有序数列的过程中采用了逆序遍历有序数列相较于顺序遍历会稍显繁琐但当数列本身已近排序状态效率会更高。时间复杂度O(N2)5、希尔排序- 插入排序的改进版。为了减少数据的移动次数在初始序列较大时取较大的步长通常取序列长度的一半此时只有两个元素比较交换一次之后步长依次减半直至步长为1即为插入排序由于此时序列已接近有序故插入元素时数据移动的次数会相对较少效率得到了提高。时间复杂度通常认为是O(N3/2)6、基数排序- 桶排序的改进版桶的大小固定为10减少了内存空间的开销。首先找出待排序列中得最大元素max并依次按max的低位到高位对所有元素排序桶元素10个元素的大小即为待排序数列元素对应数值为相等元素的个数即每次遍历待排序数列桶将其按对应数值位大小分为了10个层级桶内元素值得和为待排序数列元素个数。时间复杂度O(x*N)7、归并排序- 采用了分治和递归的思想递归分治-排序整个数列如同排序两个有序数列依次执行这个过程直至排序末端的两个元素再依次向上层输送排序好的两个子列进行排序直至整个数列有序类比二叉树的思想from down to up。时间复杂度O(NlogN)8、堆排序- 堆排序的思想借助于二叉堆中的最大堆得以实现。首先将待排序数列抽象为二叉树并构造出最大堆然后依次将最大元素即根节点元素与待排序数列的最后一个元素交换即二叉树最深层最右边的叶子结点元素每次遍历刷新最后一个元素的位置自减1直至其与首元素相交即完成排序。时间复杂度O(NlogN)9、桶排序- 实现线性排序但当元素间值得大小有较大差距时会带来内存空间的较大浪费。首先找出待排序列中得最大元素max申请内存大小为max 1的桶数组并初始化为0然后遍历排序数列并依次将每个元素作为下标的桶元素值自增1最后遍历桶元素并依次将值非0的元素下标值载入排序数列桶元素1表明有值大小相等的元素此时依次将他们载入排序数列遍历完成排序数列便为有序数列。时间复杂度O(x*N)
