æè°æåºï¼å°±æ¯è¦æ´çæ件ä¸çè®°å½ï¼ä½¿ä¹æå
³é®åéå¢(æéå)次åºæåèµ·æ¥ãå
¶ç¡®åå®ä¹å¦ä¸ï¼
è¾å
¥ï¼n个记å½R1ï¼R2ï¼â¦ï¼Rnï¼å
¶ç¸åºçå
³é®ååå«ä¸ºK1ï¼K2ï¼â¦ï¼Knã
è¾åºï¼Rilï¼Ri2ï¼â¦ï¼Rinï¼ä½¿å¾Ki1â¤Ki2â¤â¦â¤Kinã(æKi1â¥Ki2â¥â¦â¥Kin)ã è¿éï¼æ们ç®åä»ç»å ç§æåºæ¹æ³ï¼ç´æ¥æå
¥æåºãå¸å¿æåºãå泡æåºãå¿«éæåºãç´æ¥éæ©æåºï¼æä¸ææåç代ç å¨IE6ä¸æµè¯éè¿ã ç´æ¥æå
¥æåºåºæ¬ææ³
å设å¾
æåºçè®°å½åæ¾å¨æ°ç»R[1..n]ä¸ãåå§æ¶ï¼R[1]èªæ1个æåºåºï¼æ åºåºä¸ºR[2..n]ãä»i=2èµ·ç´è³i=n为æ¢ï¼ä¾æ¬¡å°R[i]æå
¥å½åçæåºåºR[1..i-1]ä¸ï¼çæå«n个记å½çæåºåºã ç®æ³æè¿°
function InsertSort(arr) { //æå
¥æåº->ç´æ¥æå
¥æ³æåº
var st = new Date();
var temp, j;
for(var i=1; i<arr.length; i++) {
if((arr[i]) < (arr[i-1])) {
temp = arr[i];
j = i-1;
do {
arr[j+1] = arr[j];
j--;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+1] = temp;
}//endif
}
status = (new Date() - st) + ' ms';
return arr;
} å¸å°æåºåºæ¬ææ³
å
åä¸ä¸ªå°äºnçæ´æ°d1ä½ä¸ºç¬¬ä¸ä¸ªå¢éï¼ææ件çå
¨é¨è®°å½åæd1个ç»ãææè·ç¦»ä¸ºdlçåæ°çè®°å½æ¾å¨åä¸ä¸ªç»ä¸ãå
å¨åç»å
è¿è¡ç´æ¥æ人æåºï¼ç¶åï¼å第äºä¸ªå¢éd2<d1éå¤ä¸è¿°çåç»åæåºï¼ç´è³æåçå¢édt=1(dt<dt-l<â¦<d2<d1)ï¼å³ææè®°å½æ¾å¨åä¸ç»ä¸è¿è¡ç´æ¥æå
¥æåºä¸ºæ¢ã
该æ¹æ³å®è´¨ä¸æ¯ä¸ç§åç»æå
¥æ¹æ³ã ç®æ³æè¿°
function ShellSort(arr) { //æå
¥æåº->å¸å¿æåº
var st = new Date();
var increment = arr.length;
do {
increment = (increment/3|0) + 1;
arr = ShellPass(arr, increment);
}
while (increment > 1) status = (new Date() - st) + ' ms';
return arr;
}
function ShellPass(arr, d) { //å¸å¿æåºå段æ§è¡å½æ°
var temp, j;
for(var i=d; i<arr.length; i++) {
if((arr[i]) < (arr[i-d])) {
temp = arr[i]; j = i-d;
do {
arr[j+d] = arr[j];
j = j-d;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+d] = temp;
}//endif
}
return arr;
} å举个ä¾å:#include "iostream.h"
void shellSort(int *arr, int len, int *p, int len1);
int main()
{
int num[15]={100,12,20,31,1,5,44,66,61,200,30,80,150,4,8};
int i;
cout<<"å¾
ææ°æ®d=(5,3,1): ";
for(i=0;i<15;i++)
{
cout<<num[i]<<" ";
}
int s[3]={5,3,1};
shellSort(num,15, s,3);
cout<<"\n";
return 0;
} void shellSort(int *arr, int len, int *p, int len1)
{
for (int i = 0; i < len1; i++)
{
int d = p[i];
for (int n = 0; n < d; n ++)
{
for (int j = n + d; j < len; j = j + d)
{
if (arr[j] < arr[j - d])
{
int tmp = arr[j];
for (int k = j - d; k >= 0 && arr[k] > tmp; k = k - d)
{
arr[k + d] = arr[k];
}
arr[k + d] = tmp;
}
}
}
cout<<"第"<<i+1<<"è¶æåºç»æï¼";
for(int m=0;m<15;m++)
cout<<arr[m]<<" ";
cout<<"\n";
}
}
å泡æåºåºæ¬ææ³
å°è¢«æåºçè®°å½æ°ç»R[1..n]åç´æåï¼æ¯ä¸ªè®°å½R[i]çä½æ¯éé为R[i].keyçæ°æ³¡ãæ ¹æ®è½»æ°æ³¡ä¸è½å¨éæ°æ³¡ä¹ä¸çååï¼ä»ä¸å¾ä¸æ«ææ°ç»Rï¼å¡æ«æå°è¿åæ¬ååçè½»æ°æ³¡ï¼å°±ä½¿å
¶åä¸"é£æµ®"ãå¦æ¤åå¤è¿è¡ï¼ç´å°æåä»»ä½ä¸¤ä¸ªæ°æ³¡é½æ¯è½»è
å¨ä¸ï¼éè
å¨ä¸ä¸ºæ¢ã
ç®æ³æè¿°
function BubbleSort(arr) { //交æ¢æåº->å泡æåº
var st = new Date();
var temp;
var exchange;
for(var i=0; i<arr.length; i++) {
exchange = false;
for(var j=arr.length-2; j>=i; j--) {
if((arr[j+1]) < (arr[j])) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
} å¿«éæåºåºæ¬ææ³
å°åé®é¢å解为è¥å¹²ä¸ªè§æ¨¡æ´å°ä½ç»æä¸åé®é¢ç¸ä¼¼çåé®é¢ãéå½å°è§£è¿äºåé®é¢ï¼ç¶åå°è¿äºåé®é¢ç解ç»å为åé®é¢ç解ã
å¨R[low..high]ä¸ä»»éä¸ä¸ªè®°å½ä½ä¸ºåºå(Pivot)ï¼ä»¥æ¤åºåå°å½åæ åºåºåå为左ãå³ä¸¤ä¸ªè¾å°çååºé´R[low..pivotpos-1)åR[pivotpos+1..high]ï¼å¹¶ä½¿å·¦è¾¹ååºé´ä¸ææè®°å½çå
³é®ååå°äºçäºåºåè®°å½(ä¸å¦¨è®°ä¸ºpivot)çå
³é®åpivot.keyï¼å³è¾¹çååºé´ä¸ææè®°å½çå
³é®åå大äºçäºpivot.keyï¼èåºåè®°å½pivotåä½äºæ£ç¡®çä½ç½®(pivotpos)ä¸ï¼å®æ é¡»åå åç»çæåºã ç®æ³æè¿°
function QuickSort(arr) { //交æ¢æåº->å¿«éæåº
if (arguments.length>1) {
var low = arguments[1];
var high = arguments[2];
} else {
var low = 0;
var high = arr.length-1;
}
if(low < high){
// function Partition
var i = low;
var j = high;
var pivot = arr[i];
while(i<j) {
while(i<j && arr[j]>=pivot)
j--;
if(i<j)
arr[i++] = arr[j];
while(i<j && arr[i]<=pivot)
i++;
if(i<j)
arr[j--] = arr[i];
}//endwhile
arr[i] = pivot;
// end function
var pivotpos = i; //Partition(arrï¼lowï¼high);
QuickSort(arr, low, pivotpos-1);
QuickSort(arr, pivotpos+1, high);
} else
return;
return arr;
} ç´æ¥éæ©æåºåºæ¬ææ³
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](1â¤iâ¤n-1)ã该è¶æåºä»å½åæ åºåºä¸éåºå
³é®åæå°çè®°å½R[k]ï¼å°å®ä¸æ åºåºç第1个记å½R[i]交æ¢ï¼ä½¿R[1..i]åR[i+1..n]åå«å为记å½ä¸ªæ°å¢å 1个çæ°æåºåºåè®°å½ä¸ªæ°åå°1个çæ°æ åºåºã
è¿æ ·ï¼n个记å½çæ件çç´æ¥éæ©æåºå¯ç»è¿n-1è¶ç´æ¥éæ©æåºå¾å°æåºç»æã ç®æ³æè¿°
function SelectSort(arr) { //éæ©æåº->ç´æ¥éæ©æåº
var st = new Date();
var temp;
for(var i=0; i<arr.length; i++) {
var k = i;
for(var j=i+1; j<arr.length; j++) {
if((arr[j]) < (arr[k]))
k = j;
}
if (k != i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
status = (new Date() - st) + ' ms';
return arr;
}
ä»è¿è¡é度ä¸æ¥çï¼å¿«éæåºæ¯æå¿«çã å¦å¤æäºåæ¥æ¾ç®æ³ä¹æ¾è¿éç®äº:template<class Type> int BinarySearch(Type a[],const Type& x,int n) { int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if (x==a[middle]) return middle; if (x>a[middle]) left=middle+1; else right=middle-1; } return -1; }
温馨提示:答案为网友推荐,仅供参考