標籤:排序演算法數據排序

每一趟從待排序的數據元素中選出最小(或最大)的一個元素,順序放在已排好序的數列的最後,直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

1簡介

排序演算法即解決以下問題的演算法:
輸入:n個數的序列<a1,a2,a3,...,an>。
輸出:原序列的一個重排<a1*,a2*,a3*,...,an*>;,使得a1*<=a2*<=a3*<=...<=an*
排序演算法有很多,包括插入排序,冒泡排序,堆排序,歸併排序,選擇排序,計數排序,基數排序,桶排序,快速排序等。插入排序,堆排序,選擇排序,歸併排序和快速排序,冒泡排序都是比較排序,它們通過對數組中的元素進行比較來實現排序,其他排序演算法則是利用非比較的其他方法來獲得有關輸入數組的排序信息。
選擇排序

2思想

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果:
①初始狀態:無序區為R[1..n],有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k],將它與無序區的第1個記錄R[1]交換,使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時,當前有序區和無序區分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k],將它與無序區的第1個記錄R交換,使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
常見的選擇排序細分為簡單選擇排序、樹形選擇排序(錦標賽排序)、堆排序。上述演算法僅是簡單選擇排序的步驟。

  
通俗的解釋:
對比數組中前一個元素跟后一個元素的大小,如果後面的元素比前面的元素小則用一個變數k來記住他的位置,接著第二次比較,前面「后一個元素」現變成了「前一個元素」,繼續跟他的「后一個元素」進行比較如果後面的元素比他要小則用變數k記住它在數組中的位置(下標),等到循環結束的時候,我們應該找到了最小的那個數的下標了,然後進行判斷,如果這個元素的下標不是第一個元素的下標,就讓第一個元素跟他交換一下值,這樣就找到整個數組中最小的數了。然後找到數組中第二小的數,讓他跟數組中第二個元素交換一下值,以此類推。
  

3排序特點

穩定
選擇排序是給每個位置選擇當前元素最小的,比如給第一個位置選擇最小的,在剩餘元素裡面給第二個元素選擇第二小的,依次類推,直到第n-1個元素,第n個元素不用選擇了,因為只剩下它一個最大的元素了。那麼,在一趟選擇,如果一個元素比當前元素小,而該小的元素又出現在一個和當前元素相等的元素後面,那麼交換后穩定性就被破壞了。比較拗口,舉個例子,序列5 8 5 2 9,我們知道第一遍選擇第1個元素5會和2交換,那麼原序列中2個5的相對前後順序就被破壞了,所以選擇排序不是一個穩定的排序演算法。

4排序實例

初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最後排序結果 13 27 38 49 49 65 76 97
#include <stdio.h>#include <stdlib.h>#include <time.h>int main(void){    int a[10],i,j,tmp,b;    srand(time(NULL));    for(i=0;i<10;i++)        a[i]=rand()%100;    for(i=0;i<10;i++)        printf("%3d",a[i]);    printf("\n");    for(i=0;i<9;i++)    {        tmp=i;        for(j=i+1;j<10;j++)         {           if(a[tmp]>a[j])           tmp=j;        }        if(i!=tmp)        {            b=a[tmp];            a[tmp]=a[i];            a[i]=b;        }    }    for(i=0;i<10;i++)    printf("%3d",a[i]);    printf("\n");    return 0;}

5語言

Pascal語言
procedure ssort(a:array of integer);{a為元素數組}
var
i,j,k,temp:integer;
begin
for i:=n downto 2 do{共n-1輪選擇}
begin
k:=1;
for j:=1 to i do
if a[j]>a[k] then k:=j;{第i輪,記錄前i個數中最大的}
begin {複合語句需要加入begin和end}
temp:=a[k];{把最大的與倒數第i個交換}
a[k]:=a[i];
a[i]:=temp;
end;
end;
end.
public class Test
{
public static int[] a = { 8,32,1,9,5,7,12,0,4,3 }; //預設整數數組
public static void main(String args[])
{
int index = a.length;//數組長度
System.out.print("排序前: ");
for (int i = 0; i < index; i++)//遍曆數組
System.out.printf("%3s",a[i]);
System.out.println("");
//選擇排序
SelectSort(index);
System.out.print("排序后: ");
for (int i = 0; i < index; i++)
System.out.printf("%3s",a[i]);
System.out.println("");
}
public static void SelectSort(int index)
{
for (int i = 0; i < index - 1; i++)
{
for (int j = i+1; j < index; j++)
{
if(a[i]>a[j])//i、j分別代表前、后角標,假如數組i角標所在的值大於j的值,就把i的值賦值給臨存變數temp,兩者再進行位置置換。
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
System.out.print("排序中: ");
for (int k = 0; k < index; k++)
System.out.printf("%3s",a[k]);
System.out.println("");
}
}
}

vb語言

之前的那個人不僅沒給選擇的,反而給了一個冒泡排序的,真是害人不淺吶
'--------------------對的---------------------
Function switch(a(),n)For i = 1 To n - 1Min = a(i)m = iFor j = i + 1 To nIf a(j) < Min ThenMin = a(j)m = jEnd IfNextk = a(i)a(i) = Mina(m) = kNextEnd Function
'--------------------錯的----------------------
'Private Sub switch(ByRef a,ByRef b)'Dim c As Integer'c = a'a = b'b = c'End Sub'-----------------------------------------------'Private Sub Command1_Click()'Dim i,j As Integer'Dim a As Variant'a = Array(12,25,58,45,33,24) '舉個例子'For i = 0 To UBound(a) - 1'For j = i + 1 To UBound(a)'If a(i) > a(j) Then'Call switch(a(i),a(j))'End If'Next j'Next i'For i = 0 To 5'Print a(i)'Next i'End SubC#語言
private int[] array;public void input_array(int v){array =new int[v];Console.WriteLine("原數組為:");for (int i = 0; i <array.Length; i++){array[i] = Convert.ToInt16(Console.ReadLine());}Select_array();}public void Select_array(){int min,temp,k=0;for (int i = 0; i < array.Length - 1; i++){min = array[i];for (int j = i+1; j < array.Length; j++){if (min > array[j]){min = array[j];k = j;}}if(array[i]!=min){temp = array[i];array[i] = array[k];array[k] = temp;}}print_array();}public void print_array(){Console.WriteLine("數組為:");for (int i = 0; i < array.Length; i++){Console.WriteLine(array[i]);}}static void Main(string[] args){Console.WriteLine("請輸入數組大小:");int value = Convert.ToInt16(Console.ReadLine());Program pro = new Program();pro.input_array(value);}QB語言
REM N 為要排序數的總數
FOR I=1 TO N-1K=IFOR J=I+1 TO NIF A(K)>A(J) THEN K=JNEXT JIF K<>I THEN SWAP A(K),A(I)NEXT IREM ENDc語言版本#include <stdio.h>//&Aring;&Aring;&ETH;ò&Euml;&atilde;·¨&micro;&Auml;&Ecirc;&micro;&Iuml;&Ouml;//&Ntilde;&iexcl;&Ocirc;&ntilde;&Aring;&Aring;&ETH;ò//&Egrave;&laquo;&frac34;&Ouml;±&auml;&Aacute;&iquest;&micro;&Auml;&para;¨&Ograve;&aring;int Min,i,j,n=10,key;int A[10];//&Ecirc;&yacute;×é&sup3;&otilde;&Ecirc;&frac14;&raquo;&macr;void chushihua(){printf("&sup3;&otilde;&Ecirc;&frac14;&raquo;&macr;A[10]&Ecirc;&yacute;×é...\n");printf("&Ccedil;&euml;&Ecirc;&auml;&Egrave;&euml;A[i]&micro;&Auml;&Ocirc;&ordf;&Euml;&Oslash;!\n");for(i=0;i<n;i++){scanf("%d",&A[i]);}}//&Aring;&Aring;&ETH;ò&sup2;&Ugrave;×÷void InsertionSort(){for(i=0;i<n-1;i++){"for(j=i+1;j<n;j++){if(A[i]>A[j]){"key = A[i];A[i] = A[j];A[j] = key;}}}}void ShowAnswer(){printf("&Aring;&Aring;&ETH;ò&ordm;ó,A&Ecirc;&yacute;×é&micro;&Auml;&Ocirc;&ordf;&Euml;&Oslash;&Aring;&Aring;&Aacute;&ETH;&Egrave;&ccedil;&Iuml;&Acirc;:\n");printf("[");for(i = 0;i<n;i++){printf("%5d",A[i]);}printf("]\n");}void main(){chushihua();InsertionSort();ShowAnswer();}Python#/usr/bin/env pythondef select(str):tmplist = list(str)count = len(str)for i in range(0,count -1):flag = ifor j in range(i,count):if tmplist[j] < tmplist[flag]:flag = jif flag != i:tmplist[i],tmplist[flag] = tmplist[flag],tmplist[i]return tmpliststr = "asdfffffffffsadfas123142141"print(select(str))Javapublic class SelectSort {    void selectsort(int[] a){        for(int i =0; i < a.length-1; ++i){            int k = i;            for(int j = i; j < a.length; ++j){                if(a[k] > a[j]){                    k = j;                }            }            if(k != i){                int temp;                temp = a[i];                a[i] = a[k];                a[k] = temp;            }        }    }}
上一篇[希爾排序]    下一篇 [學籍管理系統]

相關評論

同義詞:暫無同義詞