我遇到过那些人那些事,还有,我希望遇见你
点击上方蓝字“在北方玩弹子球”一起玩耍
public static void insertionSort(int[] array){
int tmp;
for(int i=1;i<array.length;i++){
tmp = array[i]; //将当前位置的数给tmp
int j = i;
for(;j>0&&array[j-1]>tmp;j--){
/* * 往右移,腾出左边的位置, * array[j-1]>tmp:大于号是升序排列,小于号是降序排列 */
array[j] = array[j-1];
}
//将当前位置的数插入到合适的位置
array[j] = tmp;
}
}
public static void bubbleSort(int[] array){
int tmp;
boolean flag = false; //设置是否发生交换的标志
for(int i = array.length-1;i >= 0;i--){
for(int j=0;j<i;j++){ //每一轮都找到一个最大的数放在右边
if(array[j]>array[j+1]){
tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flag = true; //发生了交换
}
}
if(!flag) break; //这一轮循环没有发生交换,说明排序已经完成,退出循环
}
}
public static void selectSort(int[] array){
for(int i = 0;i<array.length-1;i++){
int min = array[i];
int minindex = i;
for(int j = i;j<array.length;j++){
if(array[j]<min){ //选择当前最小的数
min = array[j];
minindex = j;
}
}
if(i != minindex){ //若i不是当前元素最小的,则和找到的那个元素交换
array[minindex] = array[i];
array[i] = min;
}
}
}
public static void shellSort(int[] array){
int j;
for(int gap = array.length/2; gap>0; gap /= 2){
//定义一个增长序列,即分割数组的增量,d1=N/2 dk=(d(k-1))/2
for(int i = gap; i<array.length;i++){
int tmp = array[i];
for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){
//将相距为Dk的元素进行排序
array[j] = array[j-gap];
}
array[j] = tmp;
}
}
}
/* * 堆排序 * 调整最大堆,交换根元素和最后一个元素。 * 参数说明: * a -- 待排序的数组 */
public static void heapSort(int[] a) {
int n = a.length;
int i,tmp;
// 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。
for (i = n / 2 - 1; i >= 0; i--)
maxHeapDown(a, i, n-1);
// 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
for (i = n - 1; i > 0; i--) {
// 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
// 调整a[0...i-1],使得a[0...i-1]仍然是一个最大堆。
// 即,保证a[i-1]是a[0...i-1]中的最大值。
maxHeapDown(a, 0, i-1);
}
}
/* * 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。 * 其中,N为数组下标索引值,如数组中第1个数对应的N为0。 * * 参数说明: * a -- 待排序的数组 * start -- 被下调节点的起始位置(一般为0,表示从第1个开始) * end -- 截至范围(一般为数组中最后一个元素的索引) */
public static void maxHeapDown(int[] a, int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2*c + 1; // 左(left)孩子的位置
int tmp = a[c]; // 当前(current)节点的大小
for (; l <= end; c=l,l=2*l+1) {
// "l"是左孩子,"l+1"是右孩子
if ( l < end && a[l] < a[l+1])
l++; // 左右两孩子中选择较大者,即m_heap[l+1]
if (tmp >= a[l])
break; // 调整结束
else { // 交换值
a[c] = a[l];
a[l]= tmp;
}
}
}
public class MergeSort {
private static void mergeSort(int[] array,int[] tmp,int left,int right){
if(left<right){
int center = ( left + right ) / 2;//取数组的中点
mergeSort(array,tmp,left,center);//归并排序数组的前半部分
mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
}
}
/* * 超简单的合并函数 */
private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
// TODO Auto-generated method stub
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(array[leftPos]<=array[rightPos]){
tmp[tmpPos++] = array[leftPos++];
}else{
tmp[tmpPos++] = array[rightPos++];
}
}
while(leftPos <= leftEnd){
tmp[tmpPos++] = array[leftPos++];
}
while(rightPos <= rightEnd){
tmp[tmpPos++] = array[rightPos++];
}
for(int i=0;i<numElements;i++,rightEnd--){
array[rightEnd] = tmp[rightEnd];
}
}
public static void mergeSort(int[] array){
int[] tmp = new int[array.length];//声明一个用来合并的数组
mergeSort(array,tmp,0,array.length-1);//调用排序函数,传入数字的起点和终点
}
}
/* * 快速排序 * 两个方向,左边的i下标一直往右走,当a[i] <= a[center_index], * 其中center_index是中枢元素的数组下标,而右边的j下标一直往左走,当a[j] > a[center_index] * 如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j * 交换a[j]和a[center_index],完成一趟快速排序 * 枢轴采用三数中值分割法可以优化 */
//递归快速排序
public static void quickSort(int a[]){
qSort(a, 0, a.length - 1);
}
//递归排序,利用两路划分
public static void qSort(int a[],int low,int high){
int pivot = 0;
if(low < high){
//将数组一分为二
pivot = partition(a,low,high);
//对第一部分进行递归排序
qSort(a,low,pivot);
//对第二部分进行递归排序
qSort(a,pivot + 1,high);
}
}
//partition函数,实现三数中值分割法
public static int partition(int a[],int low,int high){
int pivotkey = a[low]; //选取第一个元素为枢轴记录
while(low < high){
//将比枢轴记录小的交换到低端
while(low < high && a[high] >= pivotkey){
high--;
}
//采用替换而不是交换的方式操作
a[low] = a[high];
//将比枢轴记录大的交换到高端
while(low < high && a[low] <= pivotkey){
low++;
}
a[high] = a[low];
}
//枢纽所在位置赋值
a[low] = pivotkey;
//返回枢纽所在的位置
return low;
}
//min的值为0,max的值为待排序数组中最大值+1
public static void bucketSort(int[] data, int min, int max) {
// 缓存数组
int[] tmp = new int[data.length];
// buckets用于记录待排序元素的信息
// buckets数组定义了max-min个桶
int[] buckets = new int[max - min];
// 计算每个元素在序列出现的次数
for (int i = 0; i < data.length; i++) {
buckets[data[i] - min]++;
}
// 计算“落入”各桶内的元素在有序序列中的位置
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
// 将data中的元素完全复制到tmp数组中
System.arraycopy(data, 0, tmp, 0, data.length);
// 根据buckets数组中的信息将待排序列的各元素放入相应位置
for (int k = data.length - 1; k >= 0; k--) {
data[--buckets[tmp[k] - min]] = tmp[k];
}
}