首页 > 代码库 > 222
222
package algorithm.sort.compare.choose;
import java.util.Arrays;
/**
* 类说明
* 时间
* 空间
* 稳定性
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-28 下午03:27:47
*/
public class DirectChooseSort{
public static void main ( String[] args ){
int[] arrayA = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
directChooseSort (arrayA);
System.out.println (Arrays.toString (arrayA));
}
private static void directChooseSort ( int[] array )
{
for ( int i = 0; i < array.length; i++ )
{
int index = i;
for ( int j = i + 1; j < array.length; j++ ){
if (array[index] > array[j])
index = j;
}
if (i != index){
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
}
package algorithm.sort.compare.choose;
import java.util.Arrays;
/**
* 方法说明
* 堆排序
* 时间
* 空间
* 稳定性
* 适用情况
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午08:55:17
*/
public class HeapSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 213, 134, 65, 77, 78, 23, 43 };
method(arrayA, 0, arrayA.length);
System.out.println (Arrays.toString (arrayA));
}
private static void method( int[] array, int start, int len ){
int pos = ( len - 1 ) / 2;
for ( int i = pos; i >= 0; i-- ){
int tmp = array[start + i];
int index = i * 2 + 1;
while (index < len){
if (index + 1 < len && array[start + index] < array[start + index + 1]) // 从小到大
index += 1;
if (tmp < array[start + index]) // 从小到大
{
array[start + i] = array[start + index];
i = index;
index = i * 2 + 1;
}
else
break;
}
array[start + i] = tmp;
}
for ( int i = 0; i < len; i++ ){
int temp = array[start];
array[start] = array[start + len - 1 - i];
array[start + len - 1 - i] = temp;
// 再一次
int post = 0;
int tmp = array[start + post];
int index = 2 * post + 1;
while (index < len - 1 - i){
if (index + 1 < len - 1 - i && array[start + index] < array[start + index + 1]) // 从小到大
index += 1;
if (tmp < array[start + index]) // 从小到大
{
array[start + post] = array[start + index];
post = index;
index = post * 2 + 1;
}
else
break;
}
array[start + post] = tmp;
}
}
}
package algorithm.sort.compare.insert;
import java.util.Arrays;
/**
* 方法说明
* 折半插入排序 折半插入排序（binary insertion sort）是对插入排序算法的一种改进
* 时间
* 空间
* 稳定性
* 适用情况
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午10:03:39
*/
public class BinaryInsertSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
binaryInsertSort (arrayA);
System.out.println (Arrays.toString (arrayA));
}
private static void binaryInsertSort ( int[] array ){
for ( int i = 1; i < array.length; i++ ){
// if (array[i] > array[i - 1]) // 从大到小
if (array[i] < array[i - 1]){ // 从小到大
int tmp = array[i];
int low = 0;
int high = i - 1;
while (low <= high){
int mid = ( low + high ) >>> 1;
// if (array[mid] > tmp) // 从大到小
if (array[mid] < tmp)// 从小到大
low = mid + 1;
else
high = mid - 1;
}
for ( int j = i; j > low; j-- )
array[j] = array[j - 1];
array[low] = tmp;
}
}
}
}
package algorithm.sort.compare.insert;
import java.util.Arrays;
/**
* 方法说明
* 直接插入排序
* 时间
* 空间
* 稳定性
* 适用情况
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午10:05:29
*/
public class DirectInsertSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
directInsertSort (arrayA);
System.out.println (Arrays.toString (arrayA));
}
private static void directInsertSort ( int[] array ){
for ( int i = 1; i < array.length; i++ ){
int j;
int temp = array[i];
for ( j = i; j > 0; j-- ){
if (array[j - 1] > temp)
array[j] = array[j - 1];
else
break;
}
array[j] = temp;
}
}
}
package algorithm.sort.compare.insert;
import java.util.Arrays;
/**
* 方法说明
* 希尔排序 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入 排序算法的一种更高效的改进版本。
* 时间
* 空间
* 稳定性
* 适用情况
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午09:04:12
*/
public class ShellSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 213, 134, 65, 77, 78, 23, 43 };
shellSort (arrayA, 0, arrayA.length);
System.out.println (Arrays.toString (arrayA));
}
private static void shellSort ( int[] array, int start, int len ){
int power = 1;
while (( power + 1 ) * 2 < len)
power = ( power + 1 ) * 2 - 1;
for ( int k = power; k >= 1; k = ( k + 1 ) / 2 - 1 ){
for ( int i = 0; i < k; i++ ){
if (len - i <= 1)
break;
int tmp;
for ( int j = start + i + k; j < start + len; j += k ){
tmp = array[j];
int m = j;
for ( ; m > start + i; m -= k )
{
if (array[m - k] > tmp) // 从小到大
array[m] = array[m - k];
else
break;
}
array[m] = tmp;
}
}
}
}
}
package algorithm.sort.compare.merge;
import java.util.Arrays;
/**
* 方法说明
* 归并排序
* 时间
* 空间
* 稳定性
* 适用情况
* @param args void
* @author ex_kjkfb_chenyongh
* @date 2016-9-20 上午10:01:25
*/
public class MergeSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
mergeSort (arrayA, 0, arrayA.length - 1, new int[arrayA.length]);
System.out.println (Arrays.toString (arrayA));
}
private static void mergeSort ( int[] array, int start, int end, int[] tempArray ){
if (end <= start)
return;
int middle = ( start + end )/2;
mergeSort (array, start, middle, tempArray);
mergeSort (array, middle + 1, end, tempArray);
int k = 0, leftIndex = 0, rightIndex = end - start;
System.arraycopy (array, start, tempArray, 0, middle - start + 1);
for ( int i = 0; i < end - middle; i++ )
tempArray[end - start - i] = array[middle + i + 1];
while (k < end - start + 1){
if (tempArray[rightIndex] > tempArray[leftIndex]) // 从小到大
array[k + start] = tempArray[leftIndex++];
else
array[k + start] = tempArray[rightIndex--];
k++;
}
}
}
package algorithm.sort.compare.swap;
import java.util.Arrays;
/**
* 类说明
* 时间
* 空间
* 稳定性
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-28 下午03:31:04
*/
public class BubbleSort {
public static void main(String[] args) {
BubbleSort m = new BubbleSort();
int[] array1 = {-5, 23,-5,99,-9, 2, 5, 10, 7, 16, 17};
m.method1(array1);
System.out.println (Arrays.toString (array1));
int[] array2 = {-5, 23,-5,99,-9, 2, 5, 10, 7, 16, 17};
m.method2(array2);
System.out.println (Arrays.toString (array2));
}
/**
* 方法说明
*
* The bigger the latter
* First circulation: i=0, n number in total, compare n-1 times
* Second circulation: i=1, n-1 number in total, compare n-2 times
* No.n-1 circulation: i=n-2, just 2 number, compare 1 time
* (1+2+...+n-1)=n(n-1)/2
* @param array void
* @author ex_kjkfb_chenyongh
* @date 2016-9-18 下午03:59:35
*/
public void method1(int[] array){
int n=array.length;
for (int i = 0 ;i < n-1 ;i++ ) {
for (int j = 0 ; j < (n-i)-1; j++ ){
if ( array[j] > array[j+1] ){
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
//这种是先固定第一个，跟余下全部作比较
//第0 n-1次
//第1 n-2次
//第n-2 1次
public void method2(int[] array){
int n=array.length;
for ( int i = 0; i < n-1; i++ )
{
for ( int j = i + 1; j < n; j++ )
{
if (array[i] > array[j])
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
}
package algorithm.sort.compare.swap;
import java.util.Arrays;
/*
* 鸡尾酒排序也就是定向冒泡排序,
* 鸡尾酒搅拌排序,
* 搅拌排序 (也可以视作选择排序的一种变形),
* 涟漪排序,
* 来回排序
* or 快乐小时排序,
* 是冒泡排序的一种变形。
* 此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
*/
/**
* 类说明
* 时间
* 空间
* 稳定性
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-28 下午03:31:34
*/
public class CocktailSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 213, 134, 65, 77, 78, 23, 43 };
cocktailSort(arrayA);
System.out.println (Arrays.toString (arrayA));
}
public static void cocktailSort(int[] arr){
for(int i = 0 ; i < arr.length/2 ; i++){
for(int j = i ; j < arr.length-i-1 ; j++){ //将最小值排到队尾
if(arr[j] < arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
for(int j = arr.length-1-(i+1); j > i ; j--){//将最大值排到队头
if(arr[j] > arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}
package algorithm.sort.compare.swap;
import java.util.Arrays;
/*
* 快速排序（Quicksort）是对冒泡排序的一种改进。
* 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
* 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，
*
*
* 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，
* 然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，
* 这个过程称为一趟快速排序。
*
* 不稳定的
* */
/**
* 类说明
* 时间
* 空间
* 稳定性
* 适用情况
* @author ex_kjkfb_chenyongh
* @date 2016-9-28 下午03:31:57
*/
public class QuickSort {
public static void main(String[] args) {
int[] arrayA = new int[] { 213, 134, 65, 77, 78, 23, 43 };
method1(arrayA, 0, arrayA.length - 1);
System.out.println (Arrays.toString (arrayA));
int[] arrayB = new int[] { 213, 134, 65, 77, 78, 23, 43 };
method2(arrayB, 0, arrayB.length - 1);
System.out.println (Arrays.toString (arrayB));
int[] arrayC = new int[] { 213, 134, 65, 77, 78, 23, 43 };
method3(arrayC, 0, arrayC.length - 1);
System.out.println (Arrays.toString (arrayC));
int[] arrayD = new int[] { 213, 134, 65, 77, 78, 23, 43 };
method3(arrayD, 0, arrayD.length - 1);
System.out.println (Arrays.toString (arrayD));
}
//这种是先排好右边的大小，再把key插入到中间
private static void method1(int[] arr, int start, int end){
if (start < end)
{
int key = arr[start];
int i = start;
for ( int j = start + 1; j < end + 1; j++ )
{
if (key > arr[j])
{
int temp = arr[j];
arr[j] = arr[i + 1];
arr[i + 1] = temp;
i++;
}
}
arr[start] = arr[i];
arr[i] = key;
method1 (arr, start, i - 1);
method1(arr, i + 1, end);
}
}
public static void method2(int arr[], int low, int high){
int l=low;
int h=high;
int povit=arr[low];
while(l<h)
{
while( l<h && arr[h]>=povit) h--;
if(l<h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
while( l<h && arr[l]<=povit) l++;
if(l<h){
int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
if(l>low) method2(arr,low,l-1);
if(h<high) method2(arr,l+1,high);
}
public static void method3(int[] arr, int start, int end){
int i=start+1, j=end;
int key=arr[start];
if(start<end){
while(true){
while(arr[j]>key) j--;
while(arr[i]<key && i<j) i++;
if(i>=j) break;
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
if(arr[i]==key) j--;
else i++;
}
arr[start]=arr[j];
arr[j]=key;
}
if(start<i-1) method3(arr,start,i-1);
if(j+1<end) method3(arr,j+1,end);
}
//best
private static void method4(int[] arr, int start, int end){
int i=start, j=end;
int key=arr[start];
while(i<j){
while(j>i && arr[j]>=key) j--;
if(i<j){
arr[i]=arr[j];//arr[i]已经保存在key中，可将后面的数填入
i++;
}
while(i<j && arr[i]<=key) i++;
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=key;
method4(arr,start,i-1);
method4(arr,j+1,end);
}
}
222