1.快速排序
实现：
1.取中间一个数作为支点
2.分别在支点的左右两边进行查找，如果左边查找到比支点大，右边查找到比支点小，就交换位置，如此循环，比支点小的数就排在了左边，比支点大的就排在右边
3.左右两边再用递归排序，就可以完成排序操作
/**
*@brief 快速排序
*@params arr 数组 left 起始位置 right总点位置
*/
void quickSort(int arr[],int left,int right)
{
int i = left;
int j = right;
int pivot = arr[(left + right) / ]; // 支点
while(i <= j)
{
while(arr[i] < pivot)
{
i++;
} while(arr[j] > pivot)
{
j--;
} if(i<=j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} // 递归
if(left < j)
{
quickSort(arr,left,j);
} if(i < right)
{
quickSort(arr,i,right);
}
}
2.冒泡排序
原理：如果当前这个数比下一个数大，则交换位置，经过一次之后最大的数就排到了数组的末尾，以此类推
void bubble(inti arr[],int n)
{
int i ;
int temp;
for(i=;i<n-;i++)
{
if(arr[i] > arr[i + ])
{
temp = arr[i];
arr[i] = arr[i + ];
arr[i + ] = temp;
}
} } void bubbleSort(int arr[],int n)
{
int i;
for(i = n; i>=; i--)
{
bubble(arr,i);
}
}
3.选择排序
思路：
1.首先在数组中找到最大值并记录其下标
2.然后最大值与数组下标为n-1的交换。
int findMaxPos(int arr[],int n)
{
int i;
int max = arr[];
int pos = ;
for(int i = ; i<n; i++)
{
if(arr[i] > max)
{
pos = i;
max = arr[i];
}
}
return pos;
} void selectSort(int arr[],int n)
{
while(n > )
{
int pos = findMaxPos(arr,n);
int temp = arr[pos];
arr[pos] = arr[n - ];
arr[n - ] = temp;
n--;
}
}
4.插入排序
思路：
1.首要条件：两个数及以上
2.取到当前要插入的元素，以前面一个比较，如果小于前面，则需要把前面的大数移位，直到不满足小于的条件，插入相应的位置
void insert(int arr[],int n)
{
int key = arr[n];
int i = n;
while(arr[i - ] > key)
{
arr[i] = arr[i - ];
i--;
if(i == )
{
break;
}
}
arr[i] = key;
} void insertionSort(int arr[],int n)
{
int i;
for(i=; i< n; i++)
{
insert(arr,i);
}
}
5.二分查找插入排序
/*
* 折半查找排序
* 思路：
* 1.直接插入排序中，通过二分查找待插入的位置pos
* 2.将pos + 1 到 i - 1元素往后移动一个位置
* 3.将带排序的元素复制到pos
*/ // 二分查找
/*
* 如查找的数组是： a[4] =[3,2,1,4] maxLength = 4 key对应数组下标的值;
* 第一次查找：pos = 0
* 第二次查找：pos = 1
* 第三次查找：pos = 2
* 第四次查找：
*/
int findPos(int a[],int maxLength,int key)
{
int i = , low =, hight = current - ,pos;
while(low <= hight)
{
pos = (low + hight) / ;
if(a[pos] > key){ // 向左边查找
hight = pos - ;
}else{
low = pos + ;
}else{
return pos; // 返回查找到的位置
} return -; // 没有找到
} // 插入排序
void binInsertSort(int a[])
{
int i = , temp,pos,j;
for(i = ; i<a.count; i++)
{
pos = findPos(a,i,a[i]);
temp = a[i];
for(j = i -;j >= pos;j--)
{
a[j + ] = a[j]; // 元素后移
}
a[pos] = temp;
}
}
6.归并排序
思路：就是将两个已经排好序的数组，合成一个排好序的数组
1.先把数组中单个元素看做是已经排好序的堆
2.合并两个相邻的堆，重复多次，就之后剩下两个在进行合并
int *sort(int a[],int b[])
{
int maxLength = a.length + b.length
int temp[maxLength]; int ai = ;
int bi = ;
int tempi = ;
while(ai < a.length && bi <b.length)
{
if(a[ai] < b[bi])
{
temp[tempi++] = a[ai++];
}
else{
temp[tempi++] = b[bi++];
}
} // 判断那个数组最长，把长出来的继续添加到temp数组中
while(ai < a.length) temp[tempi++] = a[ai++];
while(bi < b.length) temp[tempi++] = b[bi++]; return temp;
}
7.堆排序
思路：
1.先把要排序的数组如a[9]={20,50,20,40,70,10,80,30,60}，构造堆（有大顶堆和小顶堆）
在构造有序堆时，我们开始只需要扫描一半的元素（n/2-1 ~ 0）即可，为什么?
因为(n/2-1)~0的节点才有子节点，如图1，n=8,(n/2-1) = 3 即3 2 1 0这个四个节点才有子节点
2.筛选
3.调整堆 private static void heapSort(int[] arr) {
int len = arr.length -1;
for(int i = len/2 - 1; i >=0; i --){ //堆构造
heapAdjust(arr,i,len);
} // 执行到这里，说明根节点(a[0])是最大值或者是最小值了
while (len >=0){
swap(arr,0,len--); //将堆顶元素与尾节点交换后，长度减1，尾元素最大
heapAdjust(arr,0,len); //再次对堆进行调整
}
} public static void heapAdjust(int[] arr,int i,int len){
int left,right,j ;
while((left = 2*i+1) <= len){ //判断当前父节点有无左节点（即有无孩子节点，left为左节点）
right = left + 1; //右节点或者写 2*i+2
j = left; //j"指针指向左节点"
if(j < len && arr[left] < arr[right]) //右节点大于左节点
j ++; //当前把"指针"指向右节点
if(arr[i] < arr[j]) //将父节点与孩子节点交换（如果上面if为真，则arr[j]为右节点，如果为假arr[j]则为左节点）
swap(arr,i,j);
else //说明比孩子节点都大，直接跳出循环语句
break;
i = j;
}
}
public static void swap(int[] arr,int i,int len){
int temp = arr[i];
arr[i] = arr[len];
arr[len] = temp;
}