`
liss
  • 浏览: 842462 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

几个简单常用的排序算法(面试会遇到)

阅读更多

1:quicksort
下面这个示意图很生动的演示出来快速排序的原理。




C语言代码如下:

#include <stdio.h>
#include <stdlib.h>

viod swap (int *key1, int *key2)
{
int empty = *key1;
*key1 = *key2;
*key2 = empty;
}

int partition (int * a , int p, int r)
{
int key = a[r];
int i =p;
for (int j =p ; j<r;++j)
if (a[j]<=key)
swap (&a[j],&a[i++])
//{swap(&a[j],&a[i]);i++;}
swap(&a[i],a[r]);
return i;

}

viod quick_sort (int *a, int p, int r)
{
if (p<r )
int q = partition(a,p,r);
quit_sort(a,p,q-1);
quit_sort(a,q+1,r);
}

int main (int argc , char **argv)
{
int a[10];
for (int i = 0; i<10;++i)
scanf ("%d",&a[i]);
quit_sort (a,0,9);
for (int i = 0; i<10;++i)
printf ("%d",a[i])
printf ("\n");
return EXIT_SUCCESS;

}

这里变量i的理解对整个代码的理解很重要。


今天先写这个 Int *a 与 a 同为地址,而 *a 则为内容。注意别再混淆了。
http://blog.csdn.net/fenglibing/archive/2007/08/23/1756473.aspx。java版的几个排序算法。

 功能:选择排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

 在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环
到倒数第二个数和最后一个数比较为止。 

 选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;

 for (i=0; i<n-1; i++) /*要选择的次数:0~n-2共n-1次*/
{
min = i; /*假设当前下标为i的数最小,比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (*(x+j) < *(x+min))
{   
min = j; /*如果后面的数比前面的小,则记下它的下标*/
}
}  

if (min != i) /*如果min在循环中改变了,就需要交换数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}


/*
================================================
功能:直接插入排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

 在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;

 for (i=1; i<n; i++) /*要选择的次数:1~n-1共n-1次*/
{
/*
暂存下标为i的数。注意:下标从1开始,原因就是开始时
第一个数即下标为0的数,前面没有任何数,单单一个,认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--) /*注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j); /*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/
}

  *(x+j+1) = t; /*找到下标为i的数的放置位置*/
}
}


/*
================================================
功能:冒泡排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上
而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较
小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要
求相反时,就将它们互换。

下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的
位置k,这样可以减少外层循环扫描的次数。

 冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/

void bubble_sort(int *x, int n)
{
int j, k, h, t;

for (h=n-1; h>0; h=k) /*循环到没有比较范围*/
{
for (j=0, k=0; j<h; j++) /*每次预置k=0,循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1)) /*大的放在后面,小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t; /*完成交换*/
k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}

 


/*
================================================
功能:希尔排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。

下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。

 希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;

 for (h=n/2; h>0; h=h/2) /*控制增量*/
{
for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}

分享到:
评论

相关推荐

    IT面试笔试-各种排序算法Java实现

    【IT面试笔试中的排序算法Java实现】 在IT面试和笔试中,掌握各种排序算法的实现是必不可少的技能。本文将详细介绍几种经典的排序算法,并提供Java语言的实现代码,包括冒泡排序、插入排序、选择排序和快速排序。...

    常用面试排序算法文档

    以下是对几种经典排序算法的详细解析: 1. **插入排序(Insertion Sort)** 插入排序是一种简单的排序方法,它通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体步骤包括...

    数据结构--常用的几个排序算法

    根据给定的信息,本文将详细介绍数据结构中常用的几种排序算法:插入排序(Insertion Sort)、希尔排序(Shell Sort)、冒泡排序(Bubble Sort)、选择排序(Selection Sort)以及快速排序(Quick Sort)。...

    常用数据结构排序算法总结

    本文将对几种常见的排序算法进行详细的解析,包括冒泡排序、交换排序、选择排序和插入排序,这些都是在面试、笔试和学习过程中常遇到的基本排序方法。 1. **冒泡排序**: 冒泡排序是一种直观且基础的排序算法,...

    个人写的几个排序算法

    这里我们主要探讨的是由个人编写的几种排序算法实现,包括插入排序、冒泡排序、选择排序、堆排序、快速排序和基数排序,全部用C++语言完成。这些算法各有特点,适用于不同的场景。 1. 插入排序:插入排序是一种简单...

    C#常见算法面试题小结

    这里我们将深入探讨几种常见的排序算法,如冒泡排序、选择排序和插入排序,并分析一个递归求斐波那契数列的问题,以及模拟事件处理的简单设计模式。 首先,让我们来看冒泡排序。冒泡排序是一种简单的排序算法,它...

    五种排序算法

    在本文中,我们将探讨几种在C++中最常见的排序算法。这五种算法分别是桶排序、快速排序、归并排序、插入排序和qsort函数。每种算法都有其适用场景、优缺点、时间复杂度和空间复杂度。理解这些算法对于提升编程技能和...

    面试笔试必用-必须掌握的Java排序算法

    本篇文章将深入探讨几种主要的Java排序算法及其特点。 1. **插入排序** - **直接插入排序**:将每个元素依次与已排序的序列比较,找到合适的位置插入。在数据近乎有序的情况下效率较高,时间复杂度可达到O(n)。 -...

    几种经典排序算法,包括快速排序、冒泡排序、选择排序和堆排序

    在计算机科学领域,排序算法是数据处理中至关重要的一部分,它涉及到如何有效地重新排列...同时,这些排序算法也常作为面试中考察候选人基础能力的重要题目,熟练掌握它们对于提升编程技能和解决实际问题具有重要意义。

    用JavaScript实现的常用排序算法和数据结构的交互式概述

    常用排序算法和数据结构的交互式概述,用JavaScript实现。 还包括其他几个其他的算法挑战,类似于在编程访谈中提出的问题。 这是为了帮助您在准备面试时更好地理解计算机科学的基础知识,算法和解决问题的能力。

    排序算法总结.docx

    这里我们将讨论几种常见的排序算法,包括直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序以及基数排序。此外,我们还将提及外部排序,这是一种处理大数据量时必要的排序技术。 1. ...

    常见算法面试宝典.pdf

    算法面试宝典中提到的几种排序算法为应聘者在面试中经常遇到的问题,涵盖了比较排序中的冒泡排序、归并排序和快速排序,以及非比较排序中的计数排序。下面我将详细解释每种排序算法的原理和代码示例。 1. 冒泡排序...

    算法面试专题课(Java版),Google面试官带你高质量刷题视频教程

    本课程主要涵盖了以下几个方面的知识点: 1. **基础算法**:包括排序(如快速排序、归并排序、堆排序等)、搜索(如二分查找、广度优先搜索、深度优先搜索)以及图论的基础知识,这些都是面试中的常考内容。 2. **...

    java 排序 面试题

    ### Java排序方法面试知识点详解 在Java编程领域中,排序算法是面试中常见的...面试时,考官可能会询问排序算法的具体实现细节、时间复杂度以及适用场景等。因此,了解并掌握这些基础知识对于应对技术面试至关重要。

    面试常用的字符串算法

    本篇将基于提供的文件内容,深入解析几个核心知识点,包括自定义字符串类的基本操作实现以及两种常见的排序算法——直接插入排序和快速排序。 #### 自定义字符串类 在C++中,尽管已经有了`std::string`这样的高级...

    堆排序算法实现

    通常,这样的文件可能会包含以下几个部分: 1. **初始化堆**:首先,我们需要将待排序的序列构建成一个最大堆。这可以通过从最后一个非叶子节点(堆的中间元素)开始,自底向上执行“下沉”操作来完成,确保每个...

    java经典算法 面试

    Java经典算法面试是每个软件开发人员,特别是对Java有浓厚兴趣或从事相关工作的人士,必须掌握的关键领域。这些算法不仅在面试中常被问到,而且在实际项目开发中也发挥着重要作用,有助于提高代码质量和解决问题的...

    华为面试常用算法.rar

    在准备华为的面试时,以下几个核心的算法和数据结构知识点是必须掌握的: 1. **排序算法**:包括快速排序、归并排序、堆排序、冒泡排序、插入排序、选择排序等。其中,快速排序和归并排序是面试中常见的问题,它们...

    【面试必备】排序、查找算法总结

    接下来介绍几种常用的排序算法。 ##### 2.1 常见排序算法 常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。 - **冒泡排序**: 通过重复地遍历要排序的列表,比较相邻元素并交换它们的位置...

Global site tag (gtag.js) - Google Analytics