`

常见排序算法的分析与实现

阅读更多

本文仅实现了冒泡排序、选择排序,插入排序和快速排序,仅供参考学习。

性能体验:冒泡—>选择—>插入—>快排。

 

 

冒泡排序:

 

	/**
	 * 冒泡排序—最简单的排序 
	 * 稳定性:稳定 
	 * 时间复杂度:O(n^2)
	 */
	public void BubbleSort(int a[]) {
		// 用于交换两个数的值
		int temp;

		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - 1 - i; j++) {
				// 前后两个数比较,大的数后移(向后冒泡)
				if (a[j] > a[j + 1]) {
					temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
			// 大的数向后移动
		}
		// 结束
	}

 

 

选择排序:

 

        /**
	 * 升序 
	 * 选择排序—找出最小数,然后交换当前最小数 
	 * 稳定性:不稳定 
	 * 时间复杂度:O(n^2)
	 */
	public void SelectSort(int[] a) {
		int temp = 0;
		int min;
		int index;

		for (int i = 0; i < a.length - 1; i++) {
			min = a[i];
			index = i;
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < min) {
					// 记录最小元素的位置
					index = j;
					// 更新最小值
					min = a[j];
				}
			}
			if (i != index) {
				// 找到最小值,交换位置
				temp = a[index];
				a[index] = a[i];
				a[i] = temp;
			}
		}
	}

 

插入排序

/**
	 * 升序 
	 * 直接插入排序 
	 * 稳定性:稳定 
	 * 时间复杂度:O(n^2)
	 */

	public void InsertSort(int[] a) {
		int insertVal;
		int index;

		for (int i = 1; i < a.length; i++) {

			insertVal = a[i];
			index = i - 1;
			while (index >= 0 && insertVal < a[index]) {
				a[index + 1] = a[index];
				index--;
			}
			a[index + 1] = insertVal;
		}
	}

 

        /**
	 * 快速排序 
	 * 稳定性:不稳定,多个相同的值的相对位置(前后位置)也许会在算法结束时产生变动 
	 * 时间复杂度:O(nlogn)
	 * 空间复杂度:O(nlogn)
	 */	
	public void quicksort(int[] a, int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(a, left, right);
            quicksort(a, left, dp - 1);
            quicksort(a, dp + 1, right);
        }
    }
	
	/**
	 * @return  返回中轴位置
	 */
    public int partition(int[] a, int left, int right) {
        int pivot = a[left];
        while (left < right) {
            while (left < right && a[right] >= pivot)
                right--;
            if (left < right)
                a[left++] = a[right];
            while (left < right && a[left] <= pivot)
                left++;
            if (left < right)
                a[right--] = a[left];
        }
        a[left] = pivot;
        return left;
    }

 

测试程序入口

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SortMain s = new SortMain();
		int size = 40000000;
		// 数组必须马上分配空间,否则编译器报错
		int[] a = new int[size];
		for (int i = 0; i < a.length; i++) {
			// 取0~100随机数
			int r = (int) (Math.random() * 10000);
			a[i] = r;
//			System.out.print(r + "  ");
		}
		System.out.println();
		
		//开始时间
		Calendar car = Calendar.getInstance();
		System.out.println(car.getTime());

		// 冒泡
//		 s.BubbleSort(a);

		// 选择
//		 s.SelectSort(a);

//		// 插入
//		s.InsertSort(a);
		
		//快排
		s.quicksort(a,0, size-1);
		
		//排序结束时间
		car = Calendar.getInstance();
		System.out.println(car.getTime());

		//数组长度较小时打印数组,较大时注释掉避免死机
//		for (int i = 0; i < a.length; i++) {
//			System.out.print(a[i] + "  ");
//		}

	}

 

 

各排序算法小结

 



 

 

  • 大小: 325.5 KB
分享到:
评论

相关推荐

    C语言常见排序算法的实现

    这里我们将深入探讨在C语言中实现的六种常见排序算法:插入排序、Shell排序、堆排序、冒泡排序、快速排序以及归并排序。 1. **插入排序**:插入排序是一种简单的排序算法,它的工作原理类似于我们日常生活中的整理...

    常见排序算法的实现与性能比较

    ### 常见排序算法的实现与性能比较 #### 实验背景及目的 排序算法是计算机科学中的一个重要组成部分,广泛应用于各种数据处理场景之中。通过本实验,我们旨在实现六种常见的排序算法——合并排序、插入排序、希尔...

    算法设计与分析-1排序算法性能分析-冒泡/选择/插入/合并/快速排序-pre ppt

    本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...

    各种排序算法比较(java实现)

    `Algorithm.java`文件可能包含了这些排序算法的Java实现代码,而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme.txt`文件可能是对整个项目的简要说明,包括如何运行和...

    中科大算法导论课程实验 常见排序算法的实现与性能比较 报告

    报告的标题是“中科大算法导论课程实验 常见排序算法的实现与性能比较”,指出了本实验报告的重点在于实现并比较各类常见排序算法。 #### 描述解读 描述部分指明了实验的目的和范围,要求对六种排序算法——合并...

    java实现常见排序算法

    在编程领域,排序算法是计算机科学中的核心概念,特别是在数据结构和算法分析中。Java作为广泛应用的编程语言,提供了一种高效的方式来实现各种排序算法。本文将深入探讨Java中实现的两种主要排序类型:插入排序和...

    基于JAVA语言的常见排序算法分析与比较.zip

    在计算机科学领域,排序算法是数据结构和算法分析的重要组成部分,...在"基于JAVA语言的常见排序算法分析与比较.pdf"文件中,你将找到更详细的算法实现、性能测试和可视化示例,这将对学习和掌握Java排序算法大有裨益。

    常见排序算法打包C语言实现

    这个压缩包文件包含了希尔排序和快速排序这两种常见的排序算法的C语言实现,这些都是程序员必备的知识点。 首先,我们来详细探讨希尔排序。希尔排序,又称为希尔增量排序,是由Donald Shell于1959年提出的一种改进...

    不同排序算法实现及性能分析(研究生项目作业)

    【排序算法实现与性能分析】 排序算法在计算机科学中占据着至关重要的位置,因为它们直接影响程序执行效率。本文主要探讨了五种常见的排序算法:插入排序、冒泡排序、堆排序、合并排序和快速排序,并进行了性能分析...

    常用排序算法分析与实现(Java版)

    这篇文章主要介绍了Java编程中几种常见的排序算法及其实现。...总结来说,本文提供了Java语言中实现常见排序算法的基础框架,有助于学习者理解各种排序算法的思想并动手实践,同时加深对Java编程的理解。

    算法设计与分析课程设计—内部排序(内含实验报告)

    这个课程设计可能包含了对多种经典内部排序算法的理解、实现以及性能分析。 1. **排序算法概述**:排序是将一组无序的数据元素按照特定的顺序排列起来的过程。在计算机科学中,高效的排序对于数据库查询、数据分析...

    常见排序算法的实现

    在计算机科学领域,排序算法是数据结构与算法分析中的重要组成部分。它们用于对一组数据进行排列,以便于后续处理或优化查找效率。本项目提供了多种经典的排序算法的实现,包括冒泡排序、直接插入排序、直接选择排序...

    C#实现的常见排序算法(博客的Demo)

    本篇文章将详细探讨C#实现的四种常见排序算法:冒泡排序、选择排序、快速排序和插入排序。 1. **冒泡排序**: 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换位置,使较大的元素逐渐“浮”到数组的...

    基于JAVA语言的常见排序算法分析与比较.pdf

    整体上,本文对冒泡排序、插入排序、选择排序和归并排序这四种常见的内部排序算法进行了分析和比较。通过JAVA语言实现了这些算法,并且通过对比它们的性能,提出了各自的使用场景,旨在帮助开发者根据实际情况选择最...

    常见排序算法C++实现

    在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在C++这样的系统级编程语言中,理解和掌握各种排序算法的实现至关重要。这里我们将深入探讨标题中提到的五种排序算法——归并排序、快速排序、希尔排序...

    常见排序算法 数据结构 C语言实现

    本资源“常见排序算法 数据结构 C语言实现”提供了一系列经典的排序算法的C语言实现,这些算法经过了VC 6.0编译器的验证,确保了其功能性和可靠性。以下是关于这些排序算法的详细解释: 1. **直接选择排序**:选择...

    排序算法分析内含程序和论文

    这个压缩包文件“排序算法分析内含程序和论文”显然是一个研究项目,可能包含了作者在研究生阶段对排序算法的深入探讨,以及通过软件绘制的性能比较图表。下面将对排序算法及其相关知识进行详细解析。 首先,排序...

    快速排序算法相关分析

    快速排序算法相关分析 快速排序算法是一种有效的排序算法,虽然算法在最坏的情况下运行时间为 O(n^2),但由于平均运行时间为 O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化...

Global site tag (gtag.js) - Google Analytics