冒泡排序
冒泡排序在排序算法中比较简单,但是可以帮助我们理解不变性。
不变性是指在算法中,某些条件在算法执行时是不变的,始终为真。
/**
* 其不变性体现在out右边的数据项始终是有序的, 在整个过程中,该条件始终为真.
* 最开始的时候out右边没有数据项.
*/
public void bubbleSort() {
int out, in;
for (out = nElements - 1; out >= 1; out--) { //外循环, 从后向前
for (in = 0; in < out; in++) { //内循环, 从前向后
if (array[in] > array[in+1]) { //比较交换, 大的数据项不断后移.
long temp = array[in];
array[in] = array[in+1];
array[in+1] = temp;
}
}
}
}
选择排序
选择排序与冒泡排序一样,进行N*(N-1)/2次比较,即O(N的平方)。
/**
* 其不变性体现在下标小于等于out数据项始终是有序的, 在整个过程中,该条件始终为真.
*/
public void selectionSort() {
int out, in, min;
long temp;
for (out = 0; out < nElements; out++) {
min = out; //起始位置,最小值.
for (in = out + 1; in < nElements; in++) { //注意in从out+1的位置开始
if (array[min] > array[in]) { //如果还有更小的值
min = in; //设定新的最小值的下标
}
}
temp = array[out]; //存放每轮循环最左边的值
array[out] = array[min]; //最左边的值和新的最小值交换位置
array[min] = temp;//最左边的值和新的最小值交换位置
}
}
插入排序
/**
* 其不变性体现在下标小于out数据项是局部有序的,虽然有序,但是最终位置并未确定,因为会有位置变动的情况, 在整个过程中,该条件始终为真.
*/
public void insertionSort() {
int out, in;
for (out = 1; out < nElements; out++) { //out变量作为标记,从1开始.
long temp = array[out]; //标记的数据项出列
in = out;
while (in > 0 && array[in-1] > temp) { //while循环每一次都向右移动了一个已排序的数据项.
array[in] = array[in-1];//大的数据项右移
--in; //in变量继续左移, 直到不满足条件而无法左移
}
array[in] = temp; //在in的位置插入标记的数据项
}
}
分享到:
相关推荐
选择排序 二分排序 及时终止的选择排序 冒泡排序 及时终止的冒泡排序 快速排序 插入排序 希尔排序 堆排序 利用附加数组重排数组元素 原地重排数组元素
起泡排序是一种简单直观的排序算法,通过重复遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的...
(1)直接插入排序算法验证。 (2)快速排序算法验证。 (3)直接选择排序算法验证。 几种简单的排序算法代码
常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用...
几种简单、高效的插入排序法,直接插入排序、冒泡排序法、选择排序,代码简单明了,可直接使用。
以下是对标题“几种排序方法”和描述中提到的几种排序算法的详细介绍: 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,它通过重复遍历待排序的数组,比较相邻元素并交换(如果需要)来完成排序。这个过程会...
### Java 实现几种常见排序方法 #### 泡泡排序(Bubble Sort) 泡泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复...
选择排序是一种简单直观的算法,它的工作原理是在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)元素,然后放到已排序序列的末尾。以此类推,...
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行的,直到没有再需要交换,也就是说该数列已经排序完成。 #### 2. 实现...
本文将深入探讨由C语言实现的几种常见排序算法,包括它们的基本原理、实现细节和性能特点。 首先,让我们从最经典的排序算法——冒泡排序(Bubble Sort)开始。冒泡排序通过不断地交换相邻的不正确顺序的元素来逐步...
几种常见的排序算法是编程领域中基础且重要的知识点,它们各自有不同的特点和适用场景。本文将详细介绍这些算法,并分析其效率。 一、冒泡排序 冒泡排序是一种简单的排序算法,通过不断交换相邻的两个元素来逐步...
在这个数据结构报告中,我们将深入探讨七种不同的内排序算法:简单选择排序、冒泡排序、插入排序、快速排序、两路合并排序以及堆排序。这些排序算法在C++语言环境下进行了实现,并且包含了详细的源代码和实验报告,...
1. **冒泡排序**:这是一种简单的排序算法,通过重复遍历数组,比较相邻元素并交换位置(如果需要)来逐步将最大或最小的元素“冒”到数组的一端。C语言实现冒泡排序主要涉及两层循环,外层控制遍历次数,内层进行...
插入排序是一种简单的排序算法,其基本思想是将待排序的数据分为已排序和未排序两部分,每次取未排序部分的第一个元素,插入到已排序部分的适当位置,直到所有元素都插入完毕。插入排序在处理小规模或部分有序的数据...
### 几种内部排序算法总结 #### 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,依次比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的,...
在本压缩包中,我们主要关注的是几种简单的算法,它们都是用C语言编写的,并且配合有HTML动画演示,帮助理解和学习。以下是这些算法的详细解释: 1. 插入排序(Insertion Sort) 插入排序是一种基础且直观的排序...
这里我们将深入探讨几种最常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序算法之一,它通过不断地比较相邻元素并交换位置来实现...
在C语言中,排序是程序设计中常见的任务之一,涉及到多种不同的排序算法,每种算法都有其特定的优点和缺点。以下是一些常见的排序方法及其特点: 1. **冒泡排序 (Bubble Sorting)**: - 简单描述:通过不断地交换...