`
shuofenglxy
  • 浏览: 193860 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

几种常见的排序算法

阅读更多

这里是以前写的算法总结了。照搬过来而已。

package SortSet;

import java.math.*;

public class SortSetTest {
	// 插入排序
	public static float[] InsertSort(float x[]) {
		float temp;
		int tag;
		for (int i = 0; i < x.length; i++) {
			temp = x[i];
			tag = i;
			while (tag > 0 && x[tag - 1] >= temp) {
				x[tag] = x[tag - 1];
				tag--;
			}
			x[tag] = temp;
		}
		return x;
	}

	// 冒泡排序
	public static float[] BubbleSort(float x[]) {
		for (int i = x.length - 1; i > 1; i--) {
			for (int j = 0; j < i; j++)
				if (x[j] > x[j + 1]) {
					float temp = x[j];
					x[j] = x[j + 1];
					x[j + 1] = temp;
				}
		}
		return x;
	}

	// 快速排序
	public static void QuickSort(float x[], int left, int right) {
		int i = left, j = right;
		float pivot, temp;

		pivot = x[(left + right) / 2];
		if (i < j) {
			do {
				while (x[i] <= pivot && i < right) {
					i++;
				}
				while (x[j] >= pivot && j > left) {
					j--;
				}
				if (i <= j) {
					temp = x[i];
					x[i] = x[j];
					x[j] = temp;
					i++;
					j--;
				}
			} while (i <= j);
		}

		if (j > left)
			QuickSort(x, left, j);
		if (i < right)
			QuickSort(x, i, right);
	}

	// shell排序
	public static void ShellSort(float[] x) {

		for (int i = x.length / 2; i > 2; i /= 2) {
			for (int j = 0; j < i; j++)
				insertSort(x, j, i);
		}
		insertSort(x, 0, 1);
	}

	public static void insertSort(float[] x, int start, int incr) {
		float temp;
		for (int i = start + incr; i < x.length; i += incr) {
			for (int j = i; (j >= incr) && (x[j] < x[j - incr]); j -= incr) {
				temp = x[j];
				x[j] = x[j - incr];
				x[j - incr] = temp;
			}
		}
	}

	// 合并排序
	public static void mergeSort(float[] x, float[] temp, int l, int r) {
		int mid = (l + r) / 2;
		if (l == r)
			return;

		mergeSort(x, temp, l, mid);
		mergeSort(x, temp, mid + 1, r);
		for (int i = l; i < r + 1; i++) {
			temp[i] = x[i];
		}
		int i1 = l;
		int i2 = mid + 1;
		for (int cur = l; cur <= r; cur++) {
			if (i1 == mid + 1)
				x[cur] = temp[i2++];
			else if (i2 > r)
				x[cur] = temp[i1++];
			else if (temp[i1] <= temp[i2])
				x[cur] = temp[i1++];
			else
				x[cur] = temp[i2++];
		}
	}

	// 桶排序
	public static float[] BucketSort(float[] x) {
		float t;
		float temp[][] = new float[10][100000];
		for (int i = 0; i < 10; i++)
			for (int fx = 0; fx < 100000; fx++) {
				temp[i][fx] = -1;
			}
		int j[] = new int[10];
		int k;
		for (int p = 0; p < 10; p++)
			j[p] = 0;
		for (int i = 0; i < x.length; i++) { // 划分桶

			k = (int) Math.floor(x[i] * 10);
			temp[k][j[k]] = x[i];
			j[k]++;

		}

		for (int m = 0; m < 10; m++) { // 桶内插入排序
			for (int f = 0; f < temp[m].length; f++) {
				if (temp[m][f] == -1)
					break;
				t = temp[m][f];
				int tag = f;
				while (tag > 0 && temp[m][tag - 1] > t) {
					temp[m][tag] = temp[m][tag - 1];
					tag--;
				}
				temp[m][f] = t;
			}
		}

		int s = 0;
		for (int m = 0; m < 10; m++) { // 写回原数组
			for (int f = 0;; f++) {
				if (temp[m][f] == -1)
					break;
				x[s] = temp[m][f];
				s++;
			}
		}
		return x;
	}

	public static void main(String args[]) {
		float a[] = new float[100000];
		for (int i = 0; i < 100000; i++) {
			a[i] = (float) Math.random();

		}

		float a1[][] = new float[6][10], a2[][] = new float[6][1000], a3[][] = new float[6][10000], a4[][] = new float[6][100000];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 10; i++)
				a1[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 1000; i++)
				a2[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 10000; i++)
				a3[j][i] = a[i];
		for (int j = 0; j < 6; j++)
			for (int i = 0; i < 100000; i++)
				a4[j][i] = a[i];

		// N=10;
		System.out.println("测试数值为10时,各个排序的结果如下(对同一数组):");

		System.out.println("原数组,插入排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		InsertSort(a1[0]);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();

		System.out.println("原数组,冒泡排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		BubbleSort(a1[1]);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[1].length; pp++)
			System.out.print(a1[1][pp] + "  ");
		System.out.println();

		System.out.println("原数组,快速排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		QuickSort(a1[2], 0, a1[2].length - 1);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[2].length; pp++)
			System.out.print(a1[2][pp] + "  ");
		System.out.println();

		System.out.println("原数组,希尔排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		ShellSort(a1[3]);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[3].length; pp++)
			System.out.print(a1[3][pp] + "  ");
		System.out.println();

		System.out.println("原数组,合并排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		float[] temp1 = new float[10];
		mergeSort(a1[4], temp1, 0, a1[4].length - 1);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[4].length; pp++)
			System.out.print(a1[4][pp] + "  ");
		System.out.println();

		System.out.println("原数组,桶排序:");
		for (int pp = 0; pp < a1[0].length; pp++)
			System.out.print(a1[0][pp] + "  ");
		System.out.println();
		BucketSort(a1[5]);
		System.out.println("排序后数组:");
		for (int pp = 0; pp < a1[5].length; pp++)
			System.out.print(a1[5][pp] + "  ");
		System.out.println();

		// N=1000;
		long c = System.currentTimeMillis();
		InsertSort(a2[0]);
		long b1 = System.currentTimeMillis();
		System.out.println("N=1000插入排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a2[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时冒泡排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a2[2], 0, a2[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时快速排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a2[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时希尔排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp2 = new float[1000];
		mergeSort(a2[4], temp2, 0, a2[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时合并排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a2[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=1000时桶排序时间为:" + (b1 - c));

		// N=10000;
		c = System.currentTimeMillis();
		InsertSort(a3[0]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000插入排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a3[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时冒泡排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a3[2], 0, a3[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时快速排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a3[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时希尔排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp3 = new float[10000];
		mergeSort(a3[4], temp3, 0, a3[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时合并排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a3[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=10000时桶排序时间为:" + (b1 - c));

		// N=100000;

		c = System.currentTimeMillis();
		InsertSort(a4[0]);
		b1 = System.currentTimeMillis();

		System.out.println("N=100000插入排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BubbleSort(a4[1]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时冒泡排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		QuickSort(a4[2], 0, a4[2].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时快速排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		ShellSort(a4[3]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时希尔排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		float[] temp4 = new float[100000];
		mergeSort(a4[4], temp4, 0, a4[4].length - 1);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时合并排序时间为:" + (b1 - c));

		c = System.currentTimeMillis();
		BucketSort(a4[5]);
		b1 = System.currentTimeMillis();
		System.out.println("N=100000时桶排序时间为:" + (b1 - c));

	}
}
 

 

分享到:
评论

相关推荐

    几种常用排序算法的C语言实现

    一些常用排序算法的C语言实现,包括直接选择排序,希尔排序,直接插入排序,快速排序,归并排序,冒泡排序,堆排序

    几种常见排序算法实例

    本文将详细解析标题中提及的五种排序算法:位与、选择、冒泡、插入以及qsort,并结合在VC6.0环境下进行编译实践的情况。 1. **位与排序**: 位与操作符(`&`)在某些特定场景下可用于排序,例如在整数数组中,通过...

    几种常见排序算法代码

    几种常见的排序算法是编程领域中基础且重要的知识点,它们各自有不同的特点和适用场景。本文将详细介绍这些算法,并分析其效率。 一、冒泡排序 冒泡排序是一种简单的排序算法,通过不断交换相邻的两个元素来逐步...

    几种常见排序算法实现

    几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...

    几种常见排序算法JAVA实现.pdf

    几种常见排序算法JAVA实现.pdf

    几种常见排序算法的实现

    本文将深入探讨六种常见的排序算法:选择排序、插入排序、冒泡排序、希尔排序、快速排序以及归并排序,它们都是编程实践中不可或缺的基础知识。 1. **选择排序(Selection Sort)**: 选择排序的工作原理是每一次...

    几种常见排序算法(JAVA实现).pdf

    几种常见排序算法(JAVA实现).pdf

    几种排序算法整理

    本文将深入探讨由C语言实现的几种常见排序算法,包括它们的基本原理、实现细节和性能特点。 首先,让我们从最经典的排序算法——冒泡排序(Bubble Sort)开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...

    几种常用排序算法实现及耗时比较

    包括冒泡排序,选择排序,插入排序,希尔排序,快速排序等常用排序算法的实现并耗时比较

    设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

    设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 在本文中,我们将设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数,以取得直观感受。内部排序算法是指在内存中...

    数据结构中几种常见的排序算法之比较

    数据结构中几种常见的排序算法之比较,比较常见的冒泡排序、快速排序等

    最常见的几种排序算法,来看看

    这里我们将深入探讨几种最常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,它通过不断地比较相邻元素并交换位置来实现...

    用Java实现几种常见的排序算法

    根据提供的文件信息,本文将详细介绍如何使用Java语言来实现几种常见的排序算法,包括插入排序(Insert Sort)、冒泡排序(Bubble Sort)、选择排序(Selection Sort)以及希尔排序(Shell Sort)。这些排序算法在...

    用php实现几种常见的排序算法共6页.pdf.zip

    这份资料"用php实现几种常见的排序算法共6页.pdf.zip"显然包含了关于如何使用PHP实现几种常见排序算法的教程或笔记。 首先,让我们回顾一下几种常见的排序算法,并讨论它们在PHP中的实现: 1. **冒泡排序**...

    几种常用的排序算法源码

    本文将详细讲解标题中提到的几种排序算法:插入排序、堆排序,以及快速排序和计数排序,这些都是在实际编程中经常使用的算法。 1. **插入排序**(Insertion Sort) 插入排序是一种简单直观的排序算法,它的工作...

    Java几种常见的排序算法

    Java几种常见的排序算法

    几种内部排序算法总结

    ### 几种内部排序算法总结 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,...

Global site tag (gtag.js) - Google Analytics