一、插入排序
每次将一个待排序的数据元素，按照其关键字大小插入到前面已排好序的有序序列的适当位置，使插入以后的数据序列仍然为一个有序序列，直到整个序列成为有序序列为止。
1.直接插入排序
插入排序过程需要将待插入的元素和所有的元素进行比较
/**
* 直接插入排序
* 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
* 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
*/
public void insertSort(int[] data){
int len=data.length;//数组的长度
for(int i=1;i<len;i++){
//取数组的除第一个之外的所有值
int currentData=data[i];
int temp=i;
//数组向右移
while(temp>0&&data[temp-1]>currentData){
data[temp]=data[temp-1];
temp--;
}
data[temp]=currentData;//交换数据
}
}
2.折半插入排序
将待插入数据与当前有序序列中的平分位置的关键字数据进行比较，从而确定下一步要确定的子序列，直到找到插入的合适位置。
/**
* 折半插入法
* 直接插入排序的一种改进，在直接插入排序算法中，向有序序列中插入一个元素，插入位置是把
* 待插入元素关键字与有序序列中元素的关键字逐个比较得到的。
* @param data
*/
public void binaryInsertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (temp < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
//数组后移
for (int j = i; j >= low + 1; j--) {
array[j] = array[j - 1];
}
array[low] = temp;
}
}
3.希尔排序
先将整个待排序序列分割成若干子序列，每个子序列由相关一定长度的数据元素组成(这个相差的长度称为增量)，然后我们分别对这些子序列进行直接插入排序，一轮排序后再取第二个增量，以此类推，需要注意的是，对于希尔排序中增量的确定没有统一的规定，通常的做法是：第一个增量为待排序序列长度的二分之一(取整),然后逐渐减半(取整)，直到等于1为止。
/**
* 希尔排序方法
* @param data
* int[] data={9,2,5,15,66,4,37,3,7};
* 数组长度为9 步长len为4
*/
public void shellSort(int[] data){
int length=data.length;//数组的长度
int len=length/2;//分割集合的间隔长度，初始值为数组长度的一半（步长）
int temp;//临时变量(比较交换时使用)
int pointer;//进行比较的下标位置
//1.按每次减半分步长，直到步长为1
while(len>0){
for(int i=len;i<length;i++){
//2.计算要各当前值进行比较的位置
pointer=i-len;
temp=data[i];
//3.临时变量与集合内数据进行比较
while(pointer>=0&&temp<data[pointer]){
data[pointer+len]=data[pointer];
pointer=pointer-len;
}
data[pointer+len]=temp;
}
len/=2;//每次递减一半
}
}
二、交换排序：利用交换数据元素的位置进行排序的方法称为交换排序
1.冒泡排序
/**
* 冒泡排序法
* @param data
*/
public void maoPao(int[] data){
int len=data.length;
int temp;//临时变量
for(int j= len-1;j>1;j--){
for (int i = 0; i < j; i++) {
if(data[i]>data[i+1]){
temp=data[i];
data[i]=data[i+1];
data[i+1]=temp;
}
}
}
}
2.选择排序
/**
* 选择排序
* @param data
*/
public void selectionSort(int[] data){
int len=data.length;
int out,in;//外层和内层循环的控制变量
int min;
int temp;
for(out=0;out<len-1;out++){
min=out;
for(in=out;in<len;in++){
if(data[in]<data[min])
min=in;
}
if(min!=out){
temp=data[min];
data[min]=data[out];
data[out]=temp;
}
}
}