1 éæ©æåº
å·²ç¥ä¸ç»æ åºæ°æ®a[1]ãa[2]ãâ¦â¦a[n]ï¼éå°å
¶æååºæåãé¦å
æ¯è¾a[1]ä¸a[2]çå¼ï¼è¥a[1]大äºa[2]å交æ¢ä¸¤è
çå¼ï¼å¦åä¸åãåæ¯è¾a[1]ä¸a[3]çå¼ï¼è¥a[1]大äºa[3]å交æ¢ä¸¤è
çå¼ï¼å¦åä¸åãåæ¯è¾a[1]ä¸a[4]ï¼ä»¥æ¤ç±»æ¨ï¼æåæ¯è¾a[1]ä¸a[n]çå¼ãè¿æ ·å¤çä¸è½®åï¼a[1]çå¼ä¸å®æ¯è¿ç»æ°æ®ä¸æå°çãåå°a[2]ä¸a[3]~a[n]以ç¸åæ¹æ³æ¯è¾ä¸è½®ï¼åa[2]çå¼ä¸å®æ¯a[2]~a[n]ä¸æå°çãåå°a[3]ä¸a[4]~a[n]以ç¸åæ¹æ³æ¯è¾ä¸è½®ï¼ä»¥æ¤ç±»æ¨ãå
±å¤çn-1è½®åa[1]ãa[2]ãâ¦â¦a[n]就以ååºæåäºã
ä¼ç¹ï¼ç¨³å®ï¼æ¯è¾æ¬¡æ°ä¸å泡æåºä¸æ ·ï¼
缺ç¹ï¼ç¸å¯¹ä¹ä¸è¿æ¯æ
¢ã
2 æå
¥æåº
å·²ç¥ä¸ç»ååºæåæ°æ®a[1]ãa[2]ãâ¦â¦a[n]ï¼ä¸ç»æ åºæ°æ®b[1]ãb[2]ãâ¦â¦b[m]ï¼éå°äºè
å并æä¸ä¸ªååºæ°åãé¦å
æ¯è¾b[1]ä¸a[1]çå¼ï¼è¥b[1]大äºa[1]ï¼åè·³è¿ï¼æ¯è¾b[1]ä¸a[2]çå¼ï¼è¥b[1]ä»ç¶å¤§äºa[2]ï¼å继ç»è·³è¿ï¼ç´å°b[1]å°äºaæ°ç»ä¸æä¸æ°æ®a[x]ï¼åå°a[x]~a[n]åå«åå移å¨ä¸ä½ï¼å°b[1]æå
¥å°åæ¥a[x]çä½ç½®è¿å°±å®æäºb[1]çæå
¥ãb[2]~b[m]ç¨ç¸åæ¹æ³æå
¥ãï¼è¥æ æ°ç»aï¼å¯å°b[1]å½ä½n=1çæ°ç»aï¼
ä¼ç¹ï¼ç¨³å®ï¼å¿«ï¼
缺ç¹ï¼æ¯è¾æ¬¡æ°ä¸ä¸å®ï¼æ¯è¾æ¬¡æ°è¶å°ï¼æå
¥ç¹åçæ°æ®ç§»å¨è¶å¤ï¼ç¹å«æ¯å½æ°æ®æ»éåºå¤§çæ¶åï¼ä½ç¨é¾è¡¨å¯ä»¥è§£å³è¿ä¸ªé®é¢ã
3 å½å¹¶æåº
ç±å¸å°å¨1959å¹´æåºï¼å称å¸å°æåº(shellæåº)ã
å·²ç¥ä¸ç»æ åºæ°æ®a[1]ãa[2]ãâ¦â¦a[n]ï¼éå°å
¶æååºæåãåç°å½nä¸å¤§æ¶ï¼æå
¥æåºçææå¾å¥½ãé¦å
åä¸å¢éd(d<n)ï¼å°a[1]ãa[1+d]ãa[1+2d]â¦â¦å为第ä¸ç»ï¼a[2]ãa[2+d]ãa[2+2d]â¦â¦å为第äºç»â¦â¦ï¼a[d]ãa[2d]ãa[3d]â¦â¦å为æåä¸ç»ä»¥æ¬¡ç±»æ¨ï¼å¨åç»å
ç¨æå
¥æåºï¼ç¶ååd'<dï¼éå¤ä¸è¿°æä½ï¼ç´å°d=1ã
ä¼ç¹ï¼å¿«ï¼æ°æ®ç§»å¨å°ï¼
缺ç¹ï¼ä¸ç¨³å®ï¼dçåå¼æ¯å¤å°ï¼åºåå¤å°ä¸ªä¸åçå¼ï¼é½æ æ³ç¡®åç¥éï¼åªè½åç»éªæ¥åã
4 å¿«éæåº
å¿«éæåºæ¯å泡æåºçæ¹è¿çï¼æ¯ç®åå·²ç¥çæå¿«çæåºæ¹æ³ã
å·²ç¥ä¸ç»æ åºæ°æ®a[1]ãa[2]ãâ¦â¦a[n]ï¼éå°å
¶æååºæåãé¦å
ä»»åæ°æ®a[x]ä½ä¸ºåºåãæ¯è¾a[x]ä¸å
¶å®æ°æ®å¹¶æåºï¼ä½¿a[x]æå¨æ°æ®ç第kä½ï¼å¹¶ä¸ä½¿a[1]~a[k-1]ä¸çæ¯ä¸ä¸ªæ°æ®<a[x]ï¼a[k+1]~a[n]ä¸çæ¯ä¸ä¸ªæ°æ®>a[x]ï¼ç¶åéç¨åæ²»ççç¥åå«å¯¹a[1]~a[k-1]åa[k+1]~a[n]两ç»æ°æ®è¿è¡å¿«éæåºã
ä¼ç¹ï¼æå¿«ï¼æ°æ®ç§»å¨å°ï¼
缺ç¹ï¼ä¸ç¨³å®ã 转èªï¼
http://zhidao.baidu.com/question/97514844.html?si=1