排序算法
1、选择排序
从数组第一个开始：i=0
将数组中第 i 个当作最小，保存最小值的数组下标：minPos=i
在剩余的数中，逐个（a[ j ]）来和 a[minPos] 对比，小的话，将数组下标值保存： minPos=j
经过循环之后，minPos保存着第 i 趟之后数组剩余值中最小的值的数组下标值
将 a[minPos] 中的值和 a[i] 中的值调换
/**选择排序
*遍历数组 然后每次遍历到一个元素之后 继续遍历该元素之后的所有元素 然后找 到最小的元素 和其换位置*/
public static int[] select(int[] array){
for (int i = 0; i < array.length; i++) {
int minPos = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minPos]){
minPos = j;
}
}
if (array[i] > array[minPos]){
int temp = array[i];
array[i] = array[minPos];
array[minPos] = temp;
}
}
return array;
}
2、插入排序
同样逐个遍历数组,
每次第 i 个值和前一个值对比，第 i 个值小的话往前挪，第 i -1（-2、-3、-4）个值往后挪，因为从头开始排序,所以前面拍完的值都是按大小拍的，因此只要第 i 个值大于第 i -1个值，说明都比前面大。
/***插入排序
*相当于 从0开始一直++ 然后一直排列索引跟之前的元素
* */
public static int[] insert(int[] array){
for (int i = 1; i < array.length; i++) {
int temp = array[i];
for (int j = i - 1; j >= 0 ; j--) {
if (array[j] > temp ){
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
3、快速排序
在快排中要设定分水岭 就是随机一个元素，一般为数组第一个值 然后比他小的放置到其左边 比其大的在有边
设定两个游标，左边开始的为low，右边开始的为high（length-1）
首先从右边开始，high不断-1，直到遇到比base小的，和base交换，然后左边开始，low不断+1，直到遇到比base大的，和base交换，一直循环到 low=high ，第一次排序完成，以这个相等的这个下标值为分界线，两边各自进行之前的操作，直到拍完
/**快速排序
* 在快排中要设定分水岭 就是随机一个元素 然后比他小的放置到其左边 比其大的在有边 循环往复
* */
public static int[] quick(int[] array){
int length = array.length - 1;
sortQuick(array,0,length);
return array;
}
private static void sortQuick(int[] array, int low, int length) {
if(low < length){
int div = firstRun(array, low, length);
sortQuick(array,0,div - 1);
sortQuick(array,div + 1,length);
}
}
private static int firstRun(int[] array, int low, int length) {
int base = array[low];
while (low < length){
while (array[length] > base){
length--;
}
swrap(array,low,length);
while (array[low] < base){
low++;
}
swrap(array,low,length);
}
return low;
}
private static void swrap(int[] array, int low, int length) {
int temp = array[length];
array[length] = array[low];
array[low] = temp;
//return array;
}
4、合并排序
合并排序就是将数组一直拆分，将数组从中间拆分，左右数组各自递归拆分，直到拆到最后，在开始合并，合并的时候，先创建一个左右数组长度相加的长度数组，将左右两数组从各自左边开始，小的添加到新数组，并且该数组下标+1，直到其中一个数组添加完毕，将另外一个数组剩余值全部加进去。
/**合并排序
* 一直在分割
* 然后 两部分 一直分割 然后一直递归*/
public static int[] mesh(int[] array){
int length = array.length - 1 ;
int[] mysort = mysort(array, 0, length);
return mysort;
}
private static int[] mysort(int[] array, int low, int length) {
int mid = (length + low)/2;
if (low < length){
mysort(array,low,mid);
mysort(array,mid + 1,length);
merge(array,low,mid,length);
}
return array;
}
private static void merge(int[] array, int low, int mid, int length) {
int[] temp = new int[length - low + 1];
int i = low;
int j = mid + 1;
int n = 0;
while (i <= mid && j <= length){
if (array[i] > array[j]){
temp[n++] = array[j++];
}else {
temp[n++] = array[i++];
}
}
while (i <= mid){
temp[n++] = array[i++];
}
while (j <= length){
temp[n++] = array[j++];
}
//合并的逻辑 赋值给array
for (int k = 0; k < temp.length; k++) {
array[low + k] = temp[k];
}
}
5、堆排序
数组： a
范围：0~n
首先建堆，从数组中间元素开始到第一个，建立一个每个树都是大堆或者小堆
然后循环：从最后一个元素到以一个元素
将a[i]，和a[0]交换
从a[i]开始到a[0]建堆
void AdjustDown(int arr[], int i, int n)
{
int j = i * 2 + 1;//子节点
while (j<n)
{
if (j+1<n && arr[j] > arr[j + 1])//子节点中找较小的
{
j++;
}
if (arr[i] < arr[j])
{
break;
}
swap(arr[i],arr[j]);
i = j;
j = i * 2 + 1;
}
}
void MakeHeap(int arr[], int n)//建堆
{
int i = 0;
for (i = n / 2 - 1; i >= 0; i--)//((n-1)*2)+1 =n/2-1
{
AdjustDown(arr, i, n);
}
}
void HeapSort(int arr[],int len)
{
int i = 0;
MakeHeap(arr, len);
for (i = len - 1; i >= 0; i--)
{
swap(arr[i], arr[0]);
AdjustDown(arr, 0, i);
}
}
6、冒泡排序
基本思想：自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
public void bubbleSort(int[] a,int length){
int temp;
for(int i=0;i<length-2;i++){
boolean isChange=false;
for(int j=length-1;j>i;j--){
if(a[ j-1 ]>a[ j ]){
temp=a[ j-1 ];
a[ j-1 ]=a[ j ];
a[ j ]=temp;
isChange=true;
}
}
if(!isChange){
break;
}
}
}
7、希尔排序
取数组长度一半的值为第一个增量，后面一直减少增量为原来的一半，四舍五入。
将数组分为一个个数组，每个数组的下标相隔增量个长度，将每个数组进行插入排序
public void shellSort(int[] a){
int h;
for(h=a.length/2;h>=1;h/2+h%2?0:1){
shellInsert(a,h);
}
}
public void shellInsert(int a,int h){
int temp;
for(int i=0;i<=h;i++){
for(int j=i+h;j<a.length;j+h){
if(a[ j-h ]<a[ j ]){
break;
}else{
temp=a[ j ];
int k=j-h;
do{
a[ k+h ]=a[ k ];k=k-h;
}while(k>=0&&a[ k ]>temp);
a[ k-h ]=temp;
}
}
}
}
