冒泡排序
/**
* 冒泡排序
* 2 5 1 4 3 7 8 9 6
* 2 1 4 3 5 7 6 8 9
*/
public class PopSort implements Sort{
public int[] sort(int[] data){
for (int i = 0; i < data.length; i++) {
//每次循环将最大的元素移动到数组末尾
boolean hasMoved = false;
for (int j = 0; j < data.length-i-1; j++) {
if (data[j]>data[j+1]){
hasMoved = true;
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
if (!hasMoved){
System.out.println("提前退出:"+i);
break;
}
}
return data;
}
}
插入排序
直接插入
/**
* 插入排序
* 2 5 1 4 3 7 8 9 6
* 2 5 1 4 3 7 8 9 6
* 1 2 5 4 3 7 8 9 6
*/
public class InsertSort implements Sort{
//依次遍历每个元素并插入前面已排序的元素中
public int[] sort(int[] data) {
for (int i = 0; i < data.length; i++) {
int index = i;
int temp = data[i];
while (--index>=0){
if (data[index]>temp){
data[index+1] = data[index];
} else {
break;
}
}
data[index+1] = temp;
}
return data;
}
}
二分法插入排序
/**
* 二分法插入排序
* 插入数据时使用二分法查找插入位置
* 2 5 1 4 3 7 8 9 6
*/
public class BinaryInsertSort implements Sort{
public int[] sort(int[] data) {
for (int i = 1; i < data.length; i++) {
int temp = data[i];
int left = 0;
int right = i-1;
int mid;
//left 即元素插入的位置
while (left<=right){
mid = (left+right)/2;
if (temp>data[mid]){
left = mid+1;
}else {
right = mid-1;
}
}
//将插入位置后面的所有元素向后移动
for (int j = i - 1; j >= left ; j--) {
data[j+1] = data[j];
}
data[left] = temp;
}
return data;
}
}
选择排序
/**
* 选择排序
* 2 5 1 4 3 7 8 9 6
* 1{5 2 4 3 7 8 9 6}
* 1 2{5 4 3 7 8 9 6}
* 1 2 3{4 5 7 8 9 6}
* -----------------
* 1 2 3 4 5 6 7 8 9
*/
public class SelectSort implements Sort{
public int[] sort(int[] data){
for (int i = 0; i < data.length; i++) {
int minIndex = i;
for (int j = i; j < data.length; j++) {
if (data[j]<data[minIndex]){
minIndex = j;
}
}
if(i!=minIndex){
int temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
return data;
}
}
希尔排序
/**
* 希尔排序
* 2 5 1 4 3 7 8 9 6
* 1.根据步进长度选出待排序的数组
* 2.使用冒泡排序对待排序数组排序
* 3.修改步进长度
*/
public class HeerSort implements Sort{
public int[] sort(int[] data) {
//步进长度
int d = data.length/2;
while (d>=1){
for (int i = 0; i <= d; i++) {
//选出这一组中所有需要排序的数据
for (int j = i; j < data.length; j+=d) {
//冒泡排序这一组数据
for (int k = j; k + d < data.length; k+=d) {
if (data[k]>data[k+d]){
int temp = data[k];
data[k] = data[k+d];
data[k+d] = temp;
}
}
}
}
//修改步进长度重新排序
d = d /2;
System.out.println("---"+d);
}
return data;
}
}
堆排序
package com.execlib.sort;
/**
* 堆排序
*
* 建堆-调整堆
*/
public class HeapSort implements Sort{
public int[] sort(int[] data) {
//建堆最后一个非终端节点开始往上遍历创建大顶堆堆
for (int i = (data.length-2)/2; i >= 0 ; i--) {
buildHeap(data,i,data.length-1);
}
swapData(data,0,data.length-1);
//调整堆并取出最大的数字插到数组末尾
for (int i = data.length-2; i >0; i--) {
buildHeap(data,0,i);
swapData(data,0,i);
}
return data;
}
private void swapData(int[] data,int i,int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
/**
* 重建堆
* @param data
* @param s
* @param e
*/
private void buildHeap(int[] data, int s, int e) {
if (s==e)
return;
//调整节点和子节点间的关系
int tmp = data[s];
for (int k = 2*s+1; k <= e; k=2*k+1) {
//k k+1都是s的子节点
if (k+1<=e&&data[k]<data[k+1]){
k++;
}
//父节点大于子节点中最大的子节点
if (tmp>data[k]){
break;
}
data[s] = data[k];
s = k;
}
data[s] = tmp;
}
}
快速排序
package com.execlib.sort;
/**
* 快速排序
*/
public class QuickSort implements Sort{
public int[] sort(int[] data) {
//选取基数 比较数组中每一个元素,大于该基数则将该元素往后挪,小于该基数将元素往前挪
quickSort(data,0,data.length-1);
return data;
}
private void quickSort(int[] data, int low, int high) {
if (low>=high)
return;
int pivot = data[low];
int m = getPivotIndex(data,low,high,pivot);
//将数据分为两部分分开排序
quickSort(data,low,m-1);
quickSort(data,m+1,high);
}
/**
* 将基数移动到应该在的位置,并返回基数的位置
* @param data
* @param low
* @param high
* @param pivot
* @return
*/
private int getPivotIndex(int[] data, int low, int high,int pivot) {
while (low<high){
while (low<high&&data[high]>pivot){
high--;
}
//将该元素交换到低位
data[low] = data[high];
while (low<high&&data[low]<pivot){
low++;
}
//将该元素交换到高位
data[high] = data[low];
}
data[low] = pivot;
return low;
}
}
归并排序
package com.execlib.sort;
/**
* 归并排序
* 递归排序二分的每一部分然后调用合并函数合并
*/
public class MergeSort implements Sort{
public int[] sort(int[] data) {
mergeSort(data,0,data.length-1);
return data;
}
private void mergeSort(int[] data, int low, int high) {
if (low>=high)
return;
int mid = (low+high)/2;
mergeSort(data,low,mid);
mergeSort(data,mid+1,high);
merge(data,low,high,mid);
}
private void merge(int[] data, int low, int high, int mid) {
if (low>=high)
return;
int[] tmpArr = new int[high - low + 1];
int cur1 = low;
int cur2 = mid+1;
int i = 0;
while (cur1<=mid&&cur2<=high){
if (data[cur1]<data[cur2]){
tmpArr[i++] = data[cur1++];
}else {
tmpArr[i++] = data[cur2++];
}
}
while (cur1<=mid){
tmpArr[i++] = data[cur1++];
}
while (cur2<=high){
tmpArr[i++] = data[cur2++];
}
for (int j = 0; j <i ; j++) {
data[low+j] = tmpArr[j];
}
}
}
基数排序
package com.execlib.sort;
import java.util.ArrayList;
import java.util.List;
public class BasicSort implements Sort{
public int[] sort(int [] array){
int max = 0;//��ȡ���ֵ
for(int i = 0;i<array.length;i++){
if(max<array[i]){
max = array[i];
}
}
int times = 0;//��ȡ���ֵλ��
while(max>0){
max = max/10;
times++;
}
List<ArrayList> queue = new ArrayList<ArrayList>();//������
for(int i = 0;i<10;i++){
ArrayList q = new ArrayList<ArrayList>();
queue.add(q);
}
for(int i = 0;i<times;i++){
for(int j = 0;j<array.length;j++){
//��ȡ��Ӧ��λ��ֵ��iΪ0�Ǹ�λ��1��10λ��2�ǰ�λ��
int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
ArrayList q = queue.get(x);
q.add(array[j]);//��Ԫ����ӽ���Ӧ�±�����
// queue.set(x,q);//����
}
//��ʼ�ռ�
int count = 0;
for(int j = 0;j<10;j++){
while(queue.get(j).size()>0){
ArrayList<Integer> q = queue.get(j);//�õ�ÿһ������
array[count] = q.get(0);
q.remove(0);
count++;
}
}
}
return array;
}
public static void main(String[] args){
BasicSort basicSort = new BasicSort();
int [] a = {136,2,6,8,9,2,8,11,23,56,34,90,89,29,145,209,320,78,3};
basicSort.sort(a);
for(int n:a){
System.out.print(" "+n);
}
}
}
测试用例
package com.execlib.sort;
import java.util.ArrayList;
import java.util.Random;
public class SortTest {
public static void main(String[] args) {
//int[] ints = {2, 5, 1, 4, 3, 7, 8, 9, 6};
//构建数据集
int[] ints = new int[20];
ArrayList<Integer> dataList = new ArrayList();
for (int i = 0; i < ints.length; i++) {
dataList.add(i);
}
Random random = new Random();
for (int i = 0; i < ints.length; i++) {
ints[i] = dataList.remove(random.nextInt(dataList.size()));
}
Sort sort = null;
//sort = new SelectSort();
//sort = new PopSort();
//sort = new InsertSort();
//sort = new BinaryInsertSort();
//sort = new HeerSort();
//sort = new HeapSort();
//sort = new QuickSort();
sort = new MergeSort();
for (int temp:sort.sort(ints)) {
System.out.println(temp);
}
}
}
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
网友评论