排序

插入排序

插入排序的要点是：

将待插入的数据存储在一个临时的变量里面

将这个该数据和其前一个数据进行比较如果；比他大就将该数据的值复制到自己的位置上

当前的索引值减一，重复2

如果其前面的一个数据比小，停止比较变换，将变量里的值赋值到当前的位置上；

public void straInset(int[] a,int postion){ //1.记录待插入的数据 int data=a[postion]; //比较值，赋值，变换位置 while(a[postion-1]>data){ a[postion]=a[postion-1]; postion --; } a[postion]=data; } public void straSort(int[] a){ for(int i=2;i<a.lenth;i++){ straInset(a,i); } }

折半插入排序

要求：要求序列是有徐序的才能使用折半插入排序

步骤：

标记带插入数据序列的头和尾的位置；

找到序列的中间位置的数据，和现有的数据进行比较，如果大了，则top=min+1;else tear=min-1;

当top>tear 说明找到了数据的位置；经该数据位置之后的数据都后移一位； 在该位置添加数据；

private void binInset(int[] a,int top,int tail,data){ int len=tail+1; while(top<=tail){ int min=(top+tail)/2; if(a[min]> data) top=min+1; else tail=min-1; } for(int i=len;i>top;i--) a[i]=a[i-1]; a[top]=data; } public void binSort(int[] a){ for(int i=2;i<a.length;i++) binInsert(a,0,i-1); }

Shell排序

希尔排序源数据无任何要求：

思想：将一个大的序列按照指定的间隔来提取数据，对处于同等间隔的不同做的数据进行直插排序

步骤：

确定间隔gap,

确定组数，每一组就是一个晓得序列

对该序列进行排序，直插式排序；

public voidshellSort(int[] a){ //确定间隔 for(int gap=a.length/2;gap>0;gap/=2){ //确定组数 for(int i=gap;i>0;i--){ staInsert(a,i,gap); } } } public void straInset(int[] a,int postion,int gap){ //1.记录待插入的数据 int data=a[postion]; //比较值，赋值，变换位置 while(postion>=gap&&a[postion-gap]>data){ a[postion]=a[postion-gap]; postion -=gap; } a[postion]=data; }

冒泡排序

交换排序；

外围数据是有后往前内部循环是由前往后

比较当前说，和前面所有说的大小，小则望前移

void bubbleSort(int[] a,int len){ for(int i=len,i>0;i++){ bubblePass(a,i ); } } public void bubbleSort(int[] a,int len){ for(int i=1;i<len-1;i++){ if(a[i]>a[i+1]){ a[0]=a[i]; a[i]=a[i+1]; a[i+1]=a[0]; } } }

快速排序

思想：就是将一个数列，利用三数中值法，找到一个纽元素，并将这个纽元素放到最后的位置；

便利数列将大于他的值放在右边，小得放在左边；

步骤：

三数中值法找到中值；再将中值和R进行数据值交换

返回返回a[R],作为枢纽元（pivot）

在意pivot为枢纽元的序列中不能出现pivot值。因此进行比较调换的指针位置在R=R-1位置；

L和R的值和pivot的值进行比较；L一直左右移找到大于Pivot的值；等待；R一直左移找到小于Pivot的店，然后交换左右两边位置上的值；

重复3 ，直到L>=R结束查询，将pivot的值和L的值调换，表明L处的值大于Pivot的值；结束本次的调换；

递归查询pivot左右序列；

当序列足够小的时候擦呼入排序；

/* 进行枢纽值查找和移位，返回 */ public int getPivot(int[] a, int l, int r) { int center = (l + r) / 2; //查找 if (a[l] > a[center]) swap(a, l, center); if (a[l] > a[r]) swap(a, l, r); if (a[center] > a[r]) swap(a, center, r); //移位 swap(a, center, r); //返回 return a[r]; } public void quickSort(int[] a,int lift,int right){ if(right-lift<=3){ straSort(a,lift,right) ; }else{ //获取钮点 int pivot=getPivot(a,lift,right); //定义左右索引值； int l=lift; int r=right-1;//从倒数第二个数据进行索引，调换 while(true){ while(a[l]<pivot) l++; while(a[r]>pivot) r--; if(r>l) swap(a,l,r); else break; } //将纽结点的值交换到分割处； swap(a,l,right); //排分割结点左的序列 quickSort(a,lift,l-1); //排分割结点右的序列 quickSort(a,l+1,right); } } public void straSort(int[] a,int l,int r){ int len =r-l+1; for(int i=l+1;i<r+1;i++){ straInset(a,i); } } public void straInset(int[] a,int postion){ //1.记录待插入的数据 int data=a[postion]; //比较值，赋值，变换位置 while(a[postion-1]>data){ a[postion]=a[postion-1]; postion --; } a[postion]=data; }

归并排序

归并排序的思想：将一个序列一直分解到最小的单元，一个数据就是一个数值；然后将这些数组进行两两比较小的放到另一个数组中，如果有的数组没有插入完就将其剩下的部分接到临时数组后面

最后将临时数组的数据全部搬回原有数组的对应位置；，释放临时数组；

void merge(int[] a, int start, int center, int end) { int i, j; i = start; j = center + 1; //临时数组 int[] temp = new int[end - start + 1]; int k = 0; //比较合并存到临时数组中 while (i <= center && j <=end) { if (a[i] <= a[j]) temp[k++] = a[i++]; else if (a[i] >=a[j]) temp[k++] = a[j++]; } while (i <= center) temp[k++] = a[i++]; while (j <= end) temp[k++] = a[j++]; //重新写入元数组中 for (int h = 0; h <k; h++) a[start + h] = temp[h]; //释放资源 temp = null;//gc自动回收 } void msort(int[] a, int start, int end) { int center; if (start < end) { //找到中值进行分割 center = (end + start) / 2; //递归分割中值左右的序列 msort(a, start, center); msort(a, center + 1, end); //合并排序 merge(a, start, center, end); } else return; } public void mergeSort(int[] a) { msort(a, 0, a.length - 1); }