Skip to content

Instantly share code, notes, and snippets.

@coolcoolercool

coolcoolercool/src_冒泡排序_BubbleSortTest.java

Created May 16, 2018 07:10
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save coolcoolercool/4b54efadea2f714fdc0c979f8330c9c3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save coolcoolercool/4b54efadea2f714fdc0c979f8330c9c3 to your computer and use it in GitHub Desktop.
Download ZIP
数据结构-排序算法java实现
Raw
src_冒泡排序_BubbleSortTest.java
package 冒泡排序;
import java.util.Arrays;
public class BubbleSortTest implements ISort
{
public void sort(int[] array)
{
int temp;
for(int i = 1; i < array.length; i++)
{
//
for(int j = 0; j < array.length - 1; j++)
{
if(array[j] > array[j+1])
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
System.out.println(i + ":" + Arrays.toString(array));
}
}
public static void main(String[] args)
{
int array[] = {1,2,3,4,5,6,77,8,0,23,11};
ISort sort;
sort = new BubbleSortTest();
sort.sort(array);
for(int num : array)
System.out.print(num + " ");
}
}
Raw
src_冒泡排序_ISort.java
package 冒泡排序;
public interface ISort
{
public void sort(int[] array);
}
Raw
src_堆排序_HeadSortTest.java
package 堆排序;
import java.util.Arrays;
/*
* 堆排序
* */
public class HeadSortTest implements ISort
{
public void sort(int[] arr) {
int i,j,k,t;
int n = arr.length;
// 将 arr[0, n-1] 建成大根堆
for(i = n/2-1; i >= 0; i--) {
// 第 i个节点有右子树
while(2*i+1 < n) {
j = 2*i+1;
if((j+1) < n) {
// 右左子树小于右子树，则需要比较右子树
if(arr[j] < arr[j+1]) {
// 序号增加1，指向右子树
j++;
}
}
// 比较 i 与 j 为序号的数据
if(arr[i] < arr[j]) {
// 交换数据
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// 堆被破坏，需要重新调整
i = j;
}else{
// 比较左右子树节点均大则堆未破坏，不再需要调整
break;
}
}
}
System.out.println("源数据构成的堆："+ Arrays.toString(arr));
for(i = n-1; i > 0; i--) {
// 与第i个记录交换
t = arr[0];
arr[0] = arr[i];
arr[i] = t;
k = 0;
// 第 i 个节点有右子树
while(2*k+1 < i) {
j = 2*k + 1;
if((j + 1) < i) {
// 右左子树小于右子树，则需要比较右子树
if(arr[j] < arr[j+1]) {
// 序号增加1，指向右子树
j++;
}
}
// 比较 i 与 j 为序号的数据
if(arr[k] < arr[j]) {
// 交换数据
t = arr[k];
arr[k] = arr[j];
arr[j] = t;
// 堆被破坏，需要重新调整
k = j;
}
else
// 比较左右子树节点均大则堆未破坏，不再需要调整
break;
}
System.out.println("第"+(n-i)+"步排序结果：" + Arrays.toString(arr));
}
}
public static void main(String[] args) {
int array[] = {1,2,3,4,5,6,77,8,0,23,11};
ISort sort;
sort = new HeadSortTest();
sort.sort(array);
for(int num : array)
System.out.print(num + " ");
}
}
Raw
src_堆排序_ISort.java
package 堆排序;
public interface ISort
{
public void sort(int[] array);
}
Raw
src_希尔排序_ShellSortTest.java
package 希尔排序;
public class ShellSortTest
{
public static void shellSort(int array[])
{
int length = array.length;
int i, j,h;
int temp;
for(h = length / 2; h > 0; h = h / 2)
{
for(i = h; i < length; i++)
{
temp = array[i];
for(j = i - h; j >= 0; j -= h)
{
if(temp < array[j])
{
array[j + h] = array[j];
}
else
break;
}
array[j + h] = temp;
}
}
}
public static void main(String[] args) {
int i = 0;
int a[] = {5,4,9,7,6,0,1,3,2};
int len = a.length;
shellSort(a);
for(i = 0; i < len; i++)
System.out.print(a[i] + " ");
}
}
Raw
src_归并排序_MergeSortTest.java
package 归并排序;
//这种归并方式中的merge感觉理解有点不直观。所以使用下面哪种merge方法就舒服很多。
public class MergeSortTest
{
/*public static void Merge(int array[], int p, int q, int r)
{
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0, k = p; i < n1; i++, k++) {
L[i] = array[k];
}
for (i = 0, k = q + 1; i < n2; i++, k++) {
R[i] = array[k];
}
for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
if (L[i] > R[j]) {
array[k] = L[i];
i++;
} else {
array[k] = R[j];
j++;
}
}
if (i < n1) {
for (j = i; j < n1; j++, k++) {
array[k] = L[j];
}
}
if (i < n2) {
for (i = j; j < n2; i++, k++) {
array[k] = R[i];
}
}
}
public static void MergeSort(int array[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
MergeSort(array, p, q);
MergeSort(array, q + 1, r);
Merge(array, p, q, r);
}
}
public static void main(String[] args) {
int i = 0;
int a[] = {5, 4, 9, 8, 7, 0, 1, 3, 2};
int len = a.length;
MergeSort(a, 0, len - 1);
for (i = 0; i < len; i++) {
System.out.print(a[i] + " ");
}
}*/
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;//左指针
int j = mid + 1;//右指针
int k = 0;
//把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[j] < a[i]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
//把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
//把右边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
//把新数组中的数覆盖muns数组
for (int k2 = 0; k2 < temp.length; k2++) {
a[k2 + low] = temp[k2];
}
}
public static void mergeSort1(int[] a, int low, int high)
{
int mid = (low + high) / 2;
if (low < high) {
//左边归并
mergeSort1(a, low, mid);
//右边归并
mergeSort1(a, mid + 1, high);
//左右归并
merge(a, low, mid, high);
}
}
public static void main(String[] args) {
int a[] = {51, 48, 98, 10, 3, 1, 65, 77};
mergeSort1(a, 0, a.length - 1);
for(int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
Raw
src_快速排序_QuickSortTest.java
package 快速排序;
public class QuickSortTest
{
public static void sort(int array[], int low, int high) {
int i, j;
int index;
if (low >= high)
return;
i = low;
j = high;
index = array[i];
while (i < j)
{
while(i < j && array[j] >= index)
j--;
if(i < j)
array[i++] = array[j];
while(i < j && array[i] < index)
i++;
if(i < j)
array[j--] = array[i];
}
array[i] = index;
sort(array, low, i-1);
sort(array, i+1, high);
}
public static void quickSort(int array[])
{
sort(array,0,array.length - 1);
}
public static void main(String[] args)
{
int i = 0;
int a[] = {5,4,9,8,7,6,0,1,2,-3};
int len = a.length;
quickSort(a);
for(i = 0; i < len; i++)
System.out.print(a[i] + " ");
}
}
Raw
src_所有排序_BubbleSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:01
* @Description: 冒泡排序
* @Modified By:
*/
public class BubbleSort implements ISort{
public void sort(int[] arr) {
int tmp;
for(int i = 1; i < arr.length; i++) {
// 判断相邻两个数据的大小，并把较大的数往后冒泡
for(int j = 0; j < arr.length - 1; j++) {
if(arr[j] > arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
System.out.println(i + ":" + Arrays.toString(arr));
}
}
}
Raw
src_所有排序_HeapSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:05
* @Description: 堆排序
* @Modified By:
*/
public class HeapSort implements ISort
{
public void sort(int[] arr) {
int i,j,k,t;
int n = arr.length;
// 将 arr[0, n-1] 建成大根堆
for(i = n/2-1; i >= 0; i--) {
// 第 i个节点有右子树
while(2*i+1 < n) {
j = 2*i+1;
if((j+1) < n) {
// 右左子树小于右子树，则需要比较右子树
if(arr[j] < arr[j+1]) {
// 序号增加1，指向右子树
j++;
}
}
// 比较 i 与 j 为序号的数据
if(arr[i] < arr[j]) {
// 交换数据
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// 堆被破坏，需要重新调整
i = j;
}else{
// 比较左右子树节点均大则堆未破坏，不再需要调整
break;
}
}
}
System.out.println("源数据构成的堆："+ Arrays.toString(arr));
for(i = n-1; i > 0; i--) {
// 与第i个记录交换
t = arr[0];
arr[0] = arr[i];
arr[i] = t;
k = 0;
// 第 i 个节点有右子树
while(2*k+1 < i) {
j = 2*k + 1;
if((j + 1) < i) {
// 右左子树小于右子树，则需要比较右子树
if(arr[j] < arr[j+1]) {
// 序号增加1，指向右子树
j++;
}
}
// 比较 i 与 j 为序号的数据
if(arr[k] < arr[j]) {
// 交换数据
t = arr[k];
arr[k] = arr[j];
arr[j] = t;
// 堆被破坏，需要重新调整
k = j;
}else{
// 比较左右子树节点均大则堆未破坏，不再需要调整
break;
}
}
System.out.println("第"+(n-i)+"步排序结果：" + Arrays.toString(arr));
}
}
}
Raw
src_所有排序_InsertSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:07
* @Description: 插入排序
* @Modified By:
*/
public class InsertSort implements ISort{
public void sort(int[] arr) {
int tmp;
for(int i = 1; i < arr.length; i++) {
// 待插入数据
tmp = arr[i];
int j;
for(j = i - 1; j >= 0; j--) {
// 判断是否大于tmp，大于则后移一位
if(arr[j] > tmp) {
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = tmp;
System.out.println(i + ":" + Arrays.toString(arr));
}
}
}
Raw
src_所有排序_ISort.java
package 所有排序;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 16:59
* @Description:
* @Modified By:
*/
public interface ISort
{
public void sort(int[] arr);
}
Raw
src_所有排序_MergeSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:08
* @Description: 归并排序
* @Modified By:
*/
public class MergeSort implements ISort{
public void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int start, int end) {
if(start < end) {
int middle = (start + end) / 2;
//对左边进行递归
sort(arr, start, middle);
//对右边进行递归
sort(arr,middle + 1, end);
merge(arr, start, middle, end);
}
}
private static void merge(int[] arr, int i, int middle, int j) {
// 创建一个临时数组用来存储合并后的数据
int[] temp = new int[arr.length];
int m = i;
int n = middle + 1;
int k = i;
while(m <= middle && n <= j) {
//从两个数组中选取较小的数放入中间数组
if(arr[m] < arr[n]) {
temp[k++] = arr[m++];
}else{
temp[k++] = arr[n++];
}
}
//将剩余的部分放入中间数组
while(m <= middle) {
temp[k++] = arr[m++];
}
while(n <= j) {
temp[k++] = arr[n++];
}
//将中间数组复制回原数组
while(i <= j) {
arr[i] = temp[i++];
}
System.out.println(Arrays.toString(arr));
}
}
Raw
src_所有排序_QuickSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:09
* @Description: 快速排序
* @Modified By:
*/
public class QuickSort implements ISort{
public void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right){
int t;
int ltemp = left;
int rtemp = right;
// 分界值
int fIndex = arr[(left + right)/ 2];
while(ltemp < rtemp) {
// 从左侧开始查找比分界值大的数
while(arr[ltemp] < fIndex) {
// 元素小于分界值，继续查找
++ltemp;
}
// 从右侧开始查找比分界值小的数
while(arr[rtemp] > fIndex) {
// 元素大于分界值，继续查找
--rtemp;
}
// 如果查到的比分界值大的数的下标小于等于比分界值小的数的下标，则进行交换
if(ltemp <= rtemp) {
t = arr[ltemp];
arr[ltemp] = arr[rtemp];
arr[rtemp] = t;
--rtemp;
++ltemp;
}
if(ltemp == rtemp) {
ltemp++;
}
System.out.println( Arrays.toString(arr));
if(left < rtemp) {
quickSort(arr, left, ltemp - 1);
}
if(ltemp < right) {
quickSort(arr, rtemp + 1, right);
}
}
}
}
Raw
src_所有排序_SelectionSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:10
* @Description: 选择排序
* @Modified By:
*/
public class SelectionSort implements ISort{
public void sort(int[] arr) {
int tmp;
// 第n轮排序过程中的较小数的下标
int small;
for(int i = 0; i < arr.length - 1; i++) {
small = i;
// 找出最小的数的下标
for(int j = i + 1; j < arr.length; j++) {
if(arr[j] < arr[small]) {
small = j;
}
}
// 交换
if(small != i) {
tmp = arr[i];
arr[i] = arr[small];
arr[small] = tmp;
}
System.out.println(i + ":" + Arrays.toString(arr));
}
}
}
Raw
src_所有排序_ShellSort.java
package 所有排序;
import java.util.Arrays;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:11
* @Description: 希尔排序
* @Modified By:
*/
public class ShellSort implements ISort{
public void sort(int[] arr) {
// i表示希尔排序中的第n/2+1个元素（或者n/4+1）
// j表示希尔排序中从0到n/2的元素（n/4）
// r表示希尔排序中n/2+1或者n/4+1的值
int i, j, r, tmp;
// 划组排序
for(r = arr.length / 2; r >= 1; r = r / 2) {
for(i = r; i < arr.length; i++) {
tmp = arr[i];
j = i - r;
// 一轮排序
while(j >= 0 && tmp < arr[j]) {
arr[j+r] = arr[j];
j -= r;
}
arr[j+r] = tmp;
}
System.out.println(i + ":" + Arrays.toString(arr));
}
}
}
Raw
src_所有排序_SortClient.java
package 所有排序;
/**
* @author: zzw5005
* @date:Created in 2018/3/19 17:00
* @Description: main函数
* @Modified By:
*/
public class SortClient
{
public static void main(String[] args) {
int[] arr = {25, 11, 45, 26, 12, 78};
// 冒泡排序
ISort sort = new BubbleSort();
// 选择排序
sort = new SelectionSort();
// 直接插入排序
sort = new InsertSort();
// 希尔排序
sort = new ShellSort();
// 快速排序
sort = new QuickSort();
// 堆排序
sort = new HeapSort();
// 合并排序
sort = new MergeSort();
sort.sort(arr);
// 输出排序结果
for(int num : arr) {
System.out.println(num);
}
}
}
Raw
src_插入排序_InsertSortTest.java
package 插入排序;
public class InsertSortTest
{
public static void insertSort(int[] a)
{
if(a != null)
{
for(int i = 1; i < a.length; i++)
{
int temp = a[i], j;
for(j = i - 1; j >= 0; j--)
{
if(a[j] > temp)
{
a[j + 1] = a[j];
}
else
{
break;
}
}
a[j + 1] = temp;
}
}
}
public static void main(String[] args) {
int a[] = {1, -5, 6, 8, 1, 0, 3, 4};
insertSort(a);
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
}
Raw
src_选择排序_SelectSortTest.java
package 选择排序;
public class SelectSortTest
{
public static void selectSort(int[] a)
{
int i,j;
int temp = 0;
int flag = 0;
int n = a.length;
for(i = 0; i < n; i++)
{
temp = a[i];
flag = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < temp)
{
temp = a[j];
flag = j;
}
}
if(flag != i)
{
a[flag] = a[i];
a[i] = temp;
}
}
}
public static void main(String[] args) {
int i = 0;
int a[] = {5, 4, 9, 8, 7, 0, 1, 2, 10, -5};
selectSort(a);
for(i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println("\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment