(Java排序.docVIP

本文就是介绍一些常见的排序算法。排序是一个非常常见的应用场景，很多时候，我们需要根据自己需要排序的数据类型，来自定义排序算法，但是，在这里，我们只介绍这些基础排序算法，包括：插入排序、选择排序、冒泡排序、快速排序（重点）、堆排序、归并排序等等。看下图： 给定数组：int data[] = {9,2,7,19,100,97,63,208,55,78} 一、直接插入排序(内部排序、O(n2)、稳定) 原理：从待排序的数中选出一个来，插入到前面的合适位置。 [java] view plaincopyprint? package?com.xtfggef.algo.sort;?? ?? public?class?InsertSort?{?? ?? ????static?int?data[]?=?{?9,?2,?7,?19,?100,?97,?63,?208,?55,?78?};?? ?? ????public?static?void?insertSort()?{?? ????????int?tmp,?j?=?0;?? ????????for?(int?k?=?0;?k??data.length;?k++)?{//-----1----- ?? ????????????tmp?=?data[k];?? ????????????j?=?k?-?1;?? ????????????while?(j?=?0??tmp??data[j])?{//-----2----- ?? ????????????????data[j?+?1]?=?data[j];?? ????????????????j--;?? ????????????}?? ????????????data[j?+?1]?=?tmp;//------3------- ?? ????????}?? ????}?? ?? ????public?static?void?main(String[]?args)?{?? ????????print();?? ????????System.out.println();?? ????????insertSort();?? ????????System.out.println();?? ????????print();?? ????}?? ?? ????static?void?print()?{?? ????????for?(int?i?=?0;?i??data.length;?i++)?{?? ????????????System.out.print(data[i]?+??);?? ????????}?? ????}?? ?? }?? package com.xtfggef.algo.sort; public class InsertSort { static int data[] = { 9, 2, 7, 19, 100, 97, 63, 208, 55, 78 }; public static void insertSort() { int tmp, j = 0; for (int k = 0; k data.length; k++) {//-----1----- tmp = data[k]; j = k - 1; while (j = 0 tmp data[j]) {//-----2----- data[j + 1] = data[j]; j--; } data[j + 1] = tmp;//------3------- } } public static void main(String[] args) { print(); System.out.println(); insertSort(); System.out.println(); print(); } static void print() { for (int i = 0; i data.length; i++) { System.out.print(data[i] + ); } } } 我简单的讲解一下过程：思路上从待排序的数据中选出一个，插入到前面合适的位置，耗时点在插入方面，合适的位置意味着我们需要进行比较找出哪是合适的位置，举个例子：对于9,2,7,19,100,97,63,208,55,78这组数，第一个数9前面没有，不做操作，当第一个数完后，剩下的数就是待排序的数，我们将要从除去9开始的书中选出一个插入到前面合适的位置，拿到2后，放在tmp上，进行注释中的2处的代码，2处的代码就是通过循环找出这个合适的位置，发现比tmp大的数，立即将该